Submission #864184

#	Time	Username	Problem	Language	Result	Execution time	Memory
864184		vjudge1	Crossing (JOI21_crossing)	C++17	100 / 100	3830 ms	231412 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int n, p;
char d;
vector<int> wl, wr;
vector<vector<int> > sg, lz;
vector<vector<vector<int> > > pf;
vector<int> x(vector<int> u, vector<int> v)
{
    vector<int> an(n);
    for (int i = 0; i < n; i++)
        an[i] = (6 - u[i] - v[i]) % 3;
    return an;
}
vector<int> ct()
{
    vector<int> an(n);
    for (int i = 0; i < n; i++)
    {
        cin >> d;
        if (d == 'O')
            an[i] = 0;
        else if (d == 'I')
            an[i] = 1;
        else
            an[i] = 2;
    }
    return an;
}
void push(int i, int j)
{
    if (lz[i][j] == -1)
        return;
    sg[i][j] = pf[wr[i] - p][j][lz[i][j]] - pf[wl[i] - p][j][lz[i][j]];
    if (i < p)
        lz[2 * i][j] = lz[2 * i + 1][j] = lz[i][j];
    lz[i][j] = -1;
    return;
}
int qsum(int l, int r, int i, int j)
{
    push(i, j);
    if (wl[i] >= r || wr[i] <= l)
        return 0;
    if (wl[i] >= l && wr[i] <= r)
        return sg[i][j];
    return qsum(l, r, 2 * i, j) + qsum(l, r, 2 * i + 1, j);
}
void rset(int l, int r, int i, int j, int w)
{
    push(i, j);
    if (wl[i] >= r || wr[i] <= l)
        return;
    if (wl[i] >= l && wr[i] <= r)
    {
        lz[i][j] = w;
        push(i, j);
        return;
    }
    rset(l, r, 2 * i, j, w);
    rset(l, r, 2 * i + 1, j, w);
    sg[i][j] = sg[2 * i][j] + sg[2 * i + 1][j];
    return;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int i, j, k, q, l, r;
    bool z = false;
    cin >> n;
    vector<int> a = ct(), b = ct(), c = ct();
    vector<vector<int> > pos = {a, b, c, x(b, c), x(c, a), x(a, b), x(a, x(b, c)), x(b, x(c, a)), x(c, x(a, b))};
    p = n;
    while (p != (p & -p))
        p++;
    pf.resize(p + 1);
    for (i = 0; i <= p; i++)
    {
        pf[i].resize(9);
        for (j = 0; j < 9; j++)
        {
            pf[i][j].resize(3);
            for (k = 0; k < 3; k++)
            {
                if (i)
                {
                    pf[i][j][k] = pf[i - 1][j][k];
                    if (i <= n && pos[j][i - 1] == k)
                        pf[i][j][k]++;
                }
                else
                    pf[i][j][k] = 0;
            }
        }
    }
    cin >> q;
    vector<int> v = ct();
    wl.resize(2 * p);
    wr.resize(2 * p);
    sg.resize(2 * p);
    lz.resize(2 * p);
    for (i = p; i < 2 * p; i++)
    {
        sg[i].resize(9);
        lz[i].resize(9);
        for (j = 0; j < 9; j++)
        {
            if (i < p + n && pos[j][i - p] == v[i - p])
                sg[i][j] = 1;
            else
                sg[i][j] = 0;
            lz[i][j] = -1;
        }
        wl[i] = i;
        wr[i] = i + 1;
    }
    for (i = p - 1; i > 0; i--)
    {
        sg[i].resize(9);
        lz[i].resize(9);
        for (j = 0; j < 9; j++)
        {
            sg[i][j] = sg[2 * i][j] + sg[2 * i + 1][j];
            lz[i][j] = -1;
        }
        wl[i] = wl[2 * i];
        wr[i] = wr[2 * i + 1];
    }
    for (j = 0; j < 9; j++)
    {
        if (qsum(p, 2 * p, 1, j) == n)
            z = true;
    }
    if (z)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    while (q--)
    {
        cin >> l >> r >> d;
        if (d == 'O')
            k = 0;
        else if (d == 'I')
            k = 1;
        else
            k = 2;
        z = false;
        for (j = 0; j < 9; j++)
        {
            rset(p + l - 1, p + r, 1, j, k);
            if (qsum(p, 2 * p, 1, j) == n)
                z = true;
        }
        if (z)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}

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