Submission #771089

#	Time	Username	Problem	Language	Result	Execution time	Memory
771089		SamAnd	Crossing (JOI21_crossing)	C++17	100 / 100	1161 ms	176904 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 200005;

int myctoi(char c)
{
    if (c == 'J')
        return 0;
    else if (c == 'O')
        return 1;
    else if (c == 'I')
        return 2;
    assert(false);
    return 0;
}

int n;
char a[3][N];
char b[N];

struct ban
{
    int a[3][3][3];
    ban()
    {
        memset(a, 0, sizeof a);
    }
};

ban mer(const ban& l, const ban& r)
{
    ban res;
    for (int i = 0; i < 3; ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            for (int k = 0; k < 3; ++k)
            {
                if (l.a[i][j][k] * r.a[i][j][k] == 0)
                    res.a[i][j][k] = l.a[i][j][k] + r.a[i][j][k];
                else if (l.a[i][j][k] == r.a[i][j][k])
                    res.a[i][j][k] = l.a[i][j][k];
                else
                    res.a[i][j][k] = -1;
            }
        }
    }
    return res;
}

ban c[N * 4], t[N * 4];
int laz[N * 4];

void ave(int pos, int g)
{
    assert(g);
    laz[pos] = g;
    for (int i = 0; i < 3; ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            for (int k = 0; k < 3; ++k)
            {
                t[pos].a[i][j][k] = c[pos].a[i][j][k] * g;
            }
        }
    }
}

void shi(int pos)
{
    if (!laz[pos])
        return;
    ave(pos * 2, laz[pos]);
    ave(pos * 2 + 1, laz[pos]);
    laz[pos] = 0;
}

void bil(int tl, int tr, int pos)
{
    for (int i = tl; i <= tr; ++i)
    {
        c[pos].a[a[0][i]][a[1][i]][a[2][i]] = 1;
    }
    if (tl == tr)
    {
        int i = tl;
        t[pos].a[a[0][i]][a[1][i]][a[2][i]] = b[i] + 1;
        return;
    }
    int m = (tl + tr) / 2;
    bil(tl, m, pos * 2);
    bil(m + 1, tr, pos * 2 + 1);
    t[pos] = mer(t[pos * 2], t[pos * 2 + 1]);
}

void ubd(int tl, int tr, int l, int r, int y, int pos)
{
    if (l > r)
        return;
    if (tl == l && tr == r)
    {
        ave(pos, y);
        return;
    }
    shi(pos);
    int m = (tl + tr) / 2;
    ubd(tl, m, l, min(m, r), y, pos * 2);
    ubd(m + 1, tr, max(m + 1, l), r, y, pos * 2 + 1);
    t[pos] = mer(t[pos * 2], t[pos * 2 + 1]);
}

vector<int> gor(const vector<int>& a, const vector<int>& b)
{
    vector<int> c;
    assert(sz(a) == sz(b));
    for (int i = 0; i < sz(a); ++i)
    {
        if (a[i] == b[i])
            c.push_back(a[i]);
        else
            c.push_back(0 + 1 + 2 - a[i] - b[i]);
    }
    return c;
}

bool qryy()
{
    vector<int> v[4];
    for (int i = 0; i < 3; ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            for (int k = 0; k < 3; ++k)
            {
                if (t[1].a[i][j][k] == -1)
                    return false;
                if (t[1].a[i][j][k])
                {
                    v[0].push_back(i);
                    v[1].push_back(j);
                    v[2].push_back(k);
                    v[3].push_back(t[1].a[i][j][k] - 1);
                }
            }
        }
    }

    vector<vector<int> > vv;
    for (int i = 0; i < 3; ++i)
        vv.push_back(v[i]);

    for (int i = 0; i < sz(vv); ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            vector<int> t = gor(vv[i], vv[j]);
            bool z = false;
            for (int k = 0; k < sz(vv); ++k)
            {
                if (vv[k] == t)
                {
                    z = true;
                    break;
                }
            }
            if (!z)
                vv.push_back(t);
        }
        if (vv[i] == v[3])
            return true;
    }
    return false;
}

void solv()
{
    cin >> n;
    for (int i = 0; i < 3; ++i)
        cin >> (a[i] + 1);
    int qq;
    cin >> qq;
    cin >> (b + 1);

    for (int i = 0; i < 3; ++i)
    {
        for (int j = 1; j <= n; ++j)
            a[i][j] = myctoi(a[i][j]);
    }
    for (int i = 1; i <= n; ++i)
        b[i] = myctoi(b[i]);

    bil(1, n, 1);
    if (qryy())
        cout << "Yes\n";
    else
        cout << "No\n";
    while (qq--)
    {
        int l, r;
        char y;
        cin >> l >> r >> y;
        ubd(1, n, l, r, myctoi(y) + 1, 1);

        if (qryy())
            cout << "Yes\n";
        else
            cout << "No\n";
    }
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    //cin >> tt;
    while (tt--)
    {
        solv();
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void bil(int, int, int)':
Main.cpp:91:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   91 |         c[pos].a[a[0][i]][a[1][i]][a[2][i]] = 1;
      |                  ~~~~~~^
Main.cpp:91:33: warning: array subscript has type 'char' [-Wchar-subscripts]
   91 |         c[pos].a[a[0][i]][a[1][i]][a[2][i]] = 1;
      |                           ~~~~~~^
Main.cpp:91:42: warning: array subscript has type 'char' [-Wchar-subscripts]
   91 |         c[pos].a[a[0][i]][a[1][i]][a[2][i]] = 1;
      |                                    ~~~~~~^
Main.cpp:96:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   96 |         t[pos].a[a[0][i]][a[1][i]][a[2][i]] = b[i] + 1;
      |                  ~~~~~~^
Main.cpp:96:33: warning: array subscript has type 'char' [-Wchar-subscripts]
   96 |         t[pos].a[a[0][i]][a[1][i]][a[2][i]] = b[i] + 1;
      |                           ~~~~~~^
Main.cpp:96:42: warning: array subscript has type 'char' [-Wchar-subscripts]
   96 |         t[pos].a[a[0][i]][a[1][i]][a[2][i]] = b[i] + 1;
      |                                    ~~~~~~^

• Subtask 1: 3 / 3
• Subtask 2: 23 / 23
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51