Submission #1050599

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050599		Andrey	Crossing (JOI21_crossing)	C++14	100 / 100	161 ms	34132 KiB

Main

#include<bits/stdc++.h>
using namespace std;

int troll(char a) {
    if(a == 'J') {
        return 0;
    }
    else if(a == 'O') {
        return 1;
    }
    else {
        return 2;
    }
}

vector<int> seg(1000001);
vector<pair<int,int>> wow(1000001,{-2,-1});
vector<int> banana(1000001,-1);
int idk[1000001][3];

int no[9][3] = {{0,0,1},{0,1,0},{1,0,0},{2,2,0},{2,0,2},{0,2,2},{1,1,2},{1,2,1},{2,1,1}};
int pr[200001][3];

vector<int> a(200001);
vector<int> b(200001);
vector<int> c(200001);
vector<int> s(200001);

void upd(int l, int r, int ql, int qr, int x, int col, pair<int,int> z, int t) {
    if(l == ql && r == qr) {
        seg[x] = idk[x][col];
        wow[x] = {t,col};
        banana[x] = t;
        return;
    }
    int mid = (l+r)/2;
    z = max(z,wow[x]);
    if(qr <= mid) {
        upd(l,mid,ql,qr,x*2,col,z,t);
    }
    else if(ql > mid) {
        upd(mid+1,r,ql,qr,x*2+1,col,z,t);
    }
    else {
        upd(l,mid,ql,mid,x*2,col,z,t);
        upd(mid+1,r,mid+1,qr,x*2+1,col,z,t);
    }
    int a,b;
    if(z.first > banana[x*2]) {
        a = idk[x*2][z.second];
    }
    else {
        a = seg[x*2];
    }
    if(z.first > banana[x*2+1]) {
        b = idk[x*2+1][z.second];
    }
    else {
        b = seg[x*2+1];
    }
    seg[x] = (a&b);
    banana[x] = t;
}

void build(int l, int r, int x) {
    if(l == r) {
        seg[x] = pr[l][s[l]];
        idk[x][0] = pr[l][0];
        idk[x][1] = pr[l][1];
        idk[x][2] = pr[l][2];
        return;
    }
    int mid = (l+r)/2;
    build(l,mid,x*2);
    build(mid+1,r,x*2+1);
    idk[x][0] = (idk[x*2][0]&idk[x*2+1][0]);
    idk[x][1] = (idk[x*2][1]&idk[x*2+1][1]);
    idk[x][2] = (idk[x*2][2]&idk[x*2+1][2]);
    seg[x] = (seg[x*2]&seg[x*2+1]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,q;
    cin >> n;
    char x;
    for(int i = 0; i <= n; i++) {
        for(int j = 0; j < 3; j++) {
            pr[i][j] = 0;
        }
    }
    for(int i = 1; i <= n; i++) {
        cin >> x;
        a[i] = troll(x);
    }
    for(int i = 1; i <= n; i++) {
        cin >> x;
        b[i] = troll(x);
    }
    for(int i = 1; i <= n; i++) {
        cin >> x;
        c[i] = troll(x);
    }
    cin >> q;
    for(int i = 1; i <= n; i++) {
        cin >> x;
        s[i] = troll(x);
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < 9; j++) {
            int br = (a[i]*no[j][0]+b[i]*no[j][1]+c[i]*no[j][2])%3;
            pr[i][br]+=(1 << j);
        }
    }
    build(1,n,1);
    if(seg[1] > 0) {
        cout << "Yes\n";
    }
    else {
        cout << "No\n";
    }
    for(int i = 0; i < q; i++) {
        int l,r;
        cin >> l >> r >> x;
        int br = troll(x);
        upd(1,n,l,r,1,br,{-1,-1},i);
        if(seg[1] > 0) {
            cout << "Yes\n";
        }
        else {
            cout << "No\n";
        }
    }
    return 0;
}

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