Submission #1304866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304866		BilAktauAlmansur	Crossing (JOI21_crossing)	C++20	0 / 100	49 ms	816 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 + 7, mod1 = 1e9 + 9;

int n, m, pw[N][2], add[4 * N];
pair<int, int> tr[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].fi = ((s[lx - 1] - '0' + 1) * lx) % mod;
        tr[v].se = ((s[lx - 1] - '0' + 1) * lx) % mod1;
        return;
    }
    int m = (lx + rx) >> 1;
    build(v + v, lx, m);
    build(v + v + 1, m + 1, rx);
    tr[v].fi = (tr[v + v].fi + tr[v + v + 1].fi) % mod;
    tr[v].se = (tr[v + v].se + tr[v + v + 1].se) % mod1;
}
int calc(int l, int r, int d) {
    return (pw[r][d] - pw[l - 1][d] + 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].fi = (add[v] * calc(lx, rx, 0)) % mod;
    tr[v].se = (add[v] * calc(lx, rx, 1)) % mod1;
    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].fi = (tr[v + v].fi + tr[v + v + 1].fi) % mod;
    tr[v].se = (tr[v + v].se + tr[v + v + 1].se) % mod1;
}
pair<int, int> comb(pair<int, int> x, pair<int, int> y) {
    return {(x.fi + y.fi) % mod, (x.se + y.se) % mod1};
}
pair<int, int> get(int l, int r, int v, int lx, int rx) {
    push(v, lx, rx);
    if(lx > r || l > rx)return {0, 0};
    if(lx >= l && r >= rx)return tr[v];
    int m = (lx + rx) >> 1;
    return comb(get(l, r, v + v, lx, m), get(l, r, v + v + 1, m + 1, rx));
}
void solve() {
    cin>>n;
    for(int i = 1; i <= n; i++) {
        pw[i][0] = (pw[i - 1][0] + i) % mod;
        pw[i][1] = (pw[i - 1][1] + i) % mod1; 
    }
    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<pair<int, int>, int> mp;
    for(int i = 0; i < 9; i++) {
        int sum = 0, sum1 = 0;
        for(int j = 1; j <= n; j++) {
            sum = (sum + ((t[i][j - 1] - '0' + 1) * j) % mod) % mod;
            sum1 = (sum1 + ((t[i][j - 1] - '0' + 1) * j) % mod1) % mod1;
        }
        mp[{sum, sum1}] = 1;
    }
    int q;
    cin>>q;
    cin>>s;
    build(1, 1, n);
    pair<int, 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