Submission #1165292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165292		Hanksburger	Crossing (JOI21_crossing)	C++20	100 / 100	1951 ms	68364 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int cnt[9][200005][3], seg[9][800005], lazy[9][800005], n, q;
vector<int> vec[9], initial;
vector<int> cross(vector<int> x, vector<int> y)
{
    vector<int> res;
    for (int i=0; i<n; i++)
        res.push_back((x[i]*2+y[i]*2)%3);
    return res;
}
void push(int ii, int i, int l, int r)
{
    if (!lazy[ii][i] || l==r)
        return;
    int mid=(l+r)/2;
    seg[ii][i*2]=cnt[ii][mid][lazy[ii][i]-1]-(l==0?0:cnt[ii][l-1][lazy[ii][i]-1]);
    seg[ii][i*2+1]=cnt[ii][r][lazy[ii][i]-1]-cnt[ii][mid][lazy[ii][i]-1];
    lazy[ii][i*2]=lazy[ii][i];
    lazy[ii][i*2+1]=lazy[ii][i];
    lazy[ii][i]=0;
}
void build(int ii, int i, int l, int r)
{
    if (l==r)
    {
        seg[ii][i]=(vec[ii][l]==initial[l]);
        return;
    }
    int mid=(l+r)/2;
    build(ii, i*2, l, mid);
    build(ii, i*2+1, mid+1, r);
    seg[ii][i]=seg[ii][i*2]+seg[ii][i*2+1];
}
void update(int ii, int i, int l, int r, int ql, int qr, int x)
{
    if (ql<=l && r<=qr)
    {
        seg[ii][i]=cnt[ii][r][x]-(l==0?0:cnt[ii][l-1][x]);
        lazy[ii][i]=x+1;
        return;
    }
    push(ii, i, l, r);
    int mid=(l+r)/2;
    if (l<=qr && ql<=mid)
        update(ii, i*2, l, mid, ql, qr, x);
    if (mid<qr && ql<=r)
        update(ii, i*2+1, mid+1, r, ql, qr, x);
    seg[ii][i]=seg[ii][i*2]+seg[ii][i*2+1];
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i=0; i<3; i++)
    {
        for (int j=0; j<n; j++)
        {
            char x;
            cin >> x;
            vec[i].push_back(x=='J'?0:(x=='O'?1:2));
        }
    }
    vec[3]=cross(vec[0], vec[1]);
    vec[4]=cross(vec[1], vec[2]);
    vec[5]=cross(vec[2], vec[0]);
    vec[6]=cross(vec[2], vec[3]);
    vec[7]=cross(vec[0], vec[4]);
    vec[8]=cross(vec[1], vec[5]);
    cin >> q;
    for (int i=0; i<n; i++)
    {
        char x;
        cin >> x;
        initial.push_back(x=='J'?0:(x=='O'?1:2));
    }
    for (int i=0; i<9; i++)
    {
        for (int j=0; j<n; j++)
            for (int k=0; k<3; k++)
                cnt[i][j][k]=(j==0?0:cnt[i][j-1][k])+(vec[i][j]==k);
        build(i, 1, 0, n-1);
    }
    int OK=0;
    for (int j=0; j<9; j++)
        if (seg[j][1]==n)
            OK=1;
    cout << (OK?"Yes":"No") << '\n';
    for (int i=0; i<q; i++)
    {
        int l, r, x, ok=0;
        char xx;
        cin >> l >> r >> xx;
        l--, r--;
        x=(xx=='J'?0:(xx=='O'?1:2));
        for (int j=0; j<9; j++)
        {
            update(j, 1, 0, n-1, l, r, x);
            if (seg[j][1]==n)
                ok=1;
        }
        cout << (ok?"Yes":"No") << '\n';
    }
}

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