Submission #923004

#	Time	Username	Problem	Language	Result	Execution time	Memory
923004		PagodePaiva	Crossing (JOI21_crossing)	C++17	3 / 100	382 ms	4928 KiB

Main

#include<bits/stdc++.h>
#define N 100010

using namespace std;

int n;
int pref[N][2];
const int p = 1998109;
const int q = 1997293;
int v[N];

struct Segtree{
    array <int, 2> tree[4*N];
    int lazy[4*N];

    array <int, 2> join(array <int, 2> a, array <int, 2> b){
        array <int, 2> res;
        res[0] = (a[0] + b[0]) % p;
        res[1] = (a[1] + b[1]) % q;
        return res;
    }

    void unlazy(int node, int l, int r){
        if(lazy[node] == -1) return;
        tree[node] = {(lazy[node]*(((pref[r][0] - pref[l-1][0]) % p + p) % p)) % p, (lazy[node]*(((pref[r][1] - pref[l-1][1]) % q + q) % q)) % q};
        lazy[2*node] = lazy[node];
        lazy[2*node+1] = lazy[node];
        lazy[node] = -1;
    }

    void build(int node, int l, int r){
        lazy[node] = -1;
        if(l == r){
            tree[node] = {(v[l]*(((pref[l][0] - pref[l-1][0]) % p + p) % p)) % p, (v[l]*(((pref[l][1] - pref[l-1][1]) % q + q) % q)) % q};
            // cout << l << ' ' << r << ' ' << tree[node][0] << endl;
            return;    
        }
        int mid = (l+r)/2;
        build(2*node, l, mid);
        build(2*node+1, mid+1, r);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        // cout << l << ' ' << r << ' ' << tree[node][0] << endl;
        return;
    }

    void update(int node, int l, int r, int val, int tl, int tr){
        unlazy(node, tl, tr);
        if(l > tr or tl > r) return;
        if(tl >= l and r >= tr){
            lazy[node] = val;
            unlazy(node, tl, tr);
            return;
        }
        int mid = (tl+tr)/2;
        update(2*node, l, r, val, tl, mid);
        update(2*node+1, l, r, val, mid+1, tr);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        return;
    }

    array <int, 2> query(int node, int l, int r, int tl, int tr){
        unlazy(node, tl, tr);
        if(l > tr or tl > r) return {0, 0};
        if(tl >= l and r >= tr) return tree[node];
        int mid = (tl+tr)/2;
        return (join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr)));
    }
} seg;

array <int, 2> hasht(string st){
    array <int, 2> val = {0, 0};
    for(int i = 1;i <= n;i++){
        val[0] += ((((pref[i][0]-pref[i-1][0]) % p + p) % p)*(st[i-1] == 'J' ? 0 : (st[i-1] == 'O' ? 1 : 2))) % p;
        val[0] %= p;
        // cout << val[0] << ' ';
        // cout << st[i-1] << ' ';
        val[1] += ((((pref[i][1]-pref[i-1][1]) % q + q) % q)*(st[i-1] == 'J' ? 0 : (st[i-1] == 'O' ? 1 : 2))) % q;
        val[1] %= q;
    }
    // cout << endl;
    return val;
}

string st;

int main(){
    cin >> n;
    cin >> st;
    cin >> st;
    cin >> st;
    pref[1][0] = 1;
    pref[1][1] = 1;
    int val1 = 1, val2 = 1;
    for(int i = 2;i <= n;i++){
        val1 *= 3;
        val1 %= p;
        val2 *= 3;
        val2 %= q;
        pref[i][0] = (val1 + pref[i-1][0]) % p;
        pref[i][1] = (val2 + pref[i-1][1]) % q;
    }
    array <int, 2> val = hasht(st);
    int qr;
    cin >> qr;
    string t;
    cin >> t;
    for(int i = 1;i <= n;i++){
        v[i] = (t[i-1] == 'J' ? 0 : (t[i-1] == 'O' ? 1 : 2));
    }
    seg.build(1, 1, n);
    // for(int i = 1;i <= n;i++) cout << seg.query(1, i, i, 1, n)[0] << ' ';
    // cout << seg.query(1, 1, n, 1, n)[0] << ' ' << seg.query(1,1, n, 1, n)[1] << endl;
    if(seg.query(1, 1, n, 1, n) == val){
        cout << "Yes\n";
    }
    else{
        cout << "No\n";
    }
    // cout << val[0] << ' ' << val[1] << endl;
    while(qr--){
        int l, r;
        char c;
        cin >> l >> r;
        cin >> c;
        int x = (c == 'J' ? 0 : (c == 'O' ? 1 : 2));
        seg.update(1, l, r, x, 1, n);
        // cout << seg.query(1, 1, n, 1, n)[0] << ' ' << seg.query(1, 1, n, 1, n)[1] << endl;
        if(seg.query(1, 1, n, 1, n) == val){
            cout << "Yes\n";
        }
        else{
            cout << "No\n";
        }
    }
    return 0;
}

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