Submission #1304841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304841		BilAktauAlmansur	Crossing (JOI21_crossing)	C++20	0 / 100	44 ms	828 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
const int N = 2e5 + 7, M = 5e6 + 7, mod = 1e9 + 9;

int n, m, pw[N], tr[4 * N], add[4 * N];
string merge(string x, string y) {
    string res = "";
    for(int i = 0; i < n; i++) {
        if(x[i] == y[i])res += x[i];
        else {
            if(x[i] == 'J' && y[i] == 'O')res += 'I';
            if(x[i] == 'O' && y[i] == 'J')res += 'I';
            if(x[i] == 'I' && y[i] == 'O')res += 'J';
            if(x[i] == 'O' && y[i] == 'I')res += 'J';
            if(x[i] == 'J' && y[i] == 'I')res += 'O';
            if(x[i] == 'I' && y[i] == 'J')res += 'O';
        }
    }
    return res;
}
string t[9];
string s;
void build(int v, int lx, int rx) {
    if(lx == rx) {
        tr[v] = ((s[lx - 1] - '0' + 1) * lx) % mod;
        return;
    }
    int m = (lx + rx) >> 1;
    build(v + v, lx, m);
    build(v + v + 1, m + 1, rx);
    tr[v] = (tr[v + v] + tr[v + v + 1]) % mod;
}
int calc(int l, int r) {
    return (pw[r] - pw[l - 1] + mod) % mod;
}
void push(int v, int lx, int rx) {
    if(!add[v])return;
    if(lx != rx) {
        add[v + v] = add[v];
        add[v + v + 1] = add[v];
    }
    tr[v] = (add[v] * calc(lx, rx)) % mod;
    add[v] = 0;
}
void upd(int l, int r, int c, int v, int lx, int rx) {
    push(v, lx, rx);
    if(lx > r || l > rx)return;
    if(lx >= l && r >= rx) {
        add[v] = c;
        push(v, lx, rx);
        return;
    }
    int m = (lx + rx) >> 1;
    upd(l, r, c, v + v, lx, m);
    upd(l, r, c, v + v + 1, m + 1, rx);
    tr[v] = (tr[v + v] + tr[v + v + 1]) % mod;
}
int get(int l, int r, int v, int lx, int rx) {
    push(v, lx, rx);
    if(lx > r || l > rx)return 0;
    if(lx >= l && r >= rx)return tr[v];
    int m = (lx + rx) >> 1;
    return (get(l, r, v + v, lx, m) + get(l, r, v + v + 1, m + 1, rx)) % mod;
}
void solve() {
    cin>>n;
    pw[0] = 0;
    for(int i = 1; i <= n; i++) {
        pw[i] = (pw[i - 1] + i) % mod;
    }
    cin>>t[0]>>t[1]>>t[2];
    t[3] = merge(t[0], t[1]);
    t[4] = merge(t[0], t[2]);
    t[5] = merge(t[1], t[2]);
    t[6] = merge(t[0], t[5]);
    t[7] = merge(t[1], t[4]);
    t[8] = merge(t[2], t[3]);
    map<int, int> mp;
    for(int i = 0; i < 9; i++) {
        int sum = 0;
        for(int j = 1; j <= n; j++) {
            sum = (sum + ((t[i][j - 1] - '0' + 1) * j) % mod) % mod;
        }
        mp[sum] = 1;
    }
    int q;
    cin>>q;
    cin>>s;
    build(1, 1, n);
    int s = get(1, n, 1, 1, n);
    if(mp.count(s))cout << "Yes\n";
    else cout << "No\n";
    while(q --) {
        int l, r;
        char c;
        cin>>l>>r>>c;
        upd(l, r, (c - '0' + 1), 1, 1, n);
        s = get(1, n, 1, 1, n);
        if(mp.count(s))cout << "Yes\n";
        else cout << "No\n";
    }
}
signed main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    int T = 1;
    // cin>>T;
    while(T --)solve();
}

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