Submission #1239999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239999		trantrungkein	Crossing (JOI21_crossing)	C++20	100 / 100	259 ms	31972 KiB

Main

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 200000 + 10;

const int P = 31;

const int mod = 1e9 + 7;

string resi(string a,string b) {
    string res;
    for(int i = 0; i < a.size(); i++) res += 'J';
    for(int i = 1; i < a.size(); i++) {
        if(a[i] == b[i]) res[i] = a[i];
        else {
            bool J = false,O = false,I = false;
            if(a[i] == 'J' || b[i] == 'J') J = true;
            if(a[i] == 'O' || b[i] == 'O') O = true;
            if(a[i] == 'I' || b[i] == 'I') I = true;
            if(!J) res[i] = 'J';
            else if(!O) res[i] = 'O';
            else res[i] = 'I';
        }
    }
    return res;
}

int add(int a,int b) {
    a += b;
    if(a < 0) a += mod;
    if(a >= mod) a -= mod;
    return a;
}

int mul(int a,int b) {
    return (a * b) % mod;
}

int pw[N];

struct hes {
    // h[i] = h[i - 1] + (pw[i] * s[i] - 'a' + 1)
    // pw[i] * c + pw[i + 1] * c + pw[i + 2] * c =  c(pw[i] + pw[i + 1],pw[i + 2]...)
    string s;
    vector<int>val;
    void build(string t,int n) {
        s = t;
        val.resize(n + 1);
        for(int i = 1; i <= n; i++) val[i] = add(val[i - 1],mul(pw[i],(s[i] - 'A' + 1)));
    }
};

int st[N * 4],pref[N];
bool lazy[N * 4];
char koji[N * 4];

void push(int node,int tl,int tr) {
    if(!lazy[node]) return;
    st[node] = mul(koji[node] - 'A' + 1,add(pref[tr],-pref[tl - 1]));
    if(tl != tr) {
        lazy[node * 2] = true;
        lazy[node * 2 + 1] = true;
        koji[node * 2] = koji[node];
        koji[node * 2 + 1] = koji[node];
    }
    lazy[node] = false;
}

void modify(int node,int tl,int tr,int l,int r,char c) {
    push(node,tl,tr);
    if(tl > r || tr < l) return;
    if(tl >= l && tr <= r) {
        lazy[node] = true;
        koji[node] = c;
        push(node,tl,tr);
        return;
    }
    int mid = (tl + tr) / 2;
    modify(node * 2,tl,mid,l,r,c);
    modify(node * 2 + 1,mid + 1,tr,l,r,c);
    st[node] = add(st[node * 2],st[node * 2 + 1]);
}

int get(int node,int tl,int tr,int l,int r) {
    if(tl > r || tr < l) return 0;
    if(tl >= l && tr <= r) return st[node];
    int mid = (tl + tr) / 2;
    return add(get(node * 2,tl,mid,l,r),get(node * 2 + 1,mid + 1,tr,l,r));
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;
    pw[0] = 1;
    for(int i = 1; i <= n; i++) pw[i] = mul(pw[i - 1],P);
    for(int i = 1; i <= n; i++) pref[i] = add(pref[i - 1],pw[i]);
    set<string>st;
    string a,b,c;
    cin >> a >> b >> c;
    a = '.' + a;
    b = '.' + b;
    c = '.' + c;
    st.insert(a);
    st.insert(b);
    st.insert(c);
    st.insert(resi(a,c));
    st.insert(resi(b,c));
    st.insert(resi(a,b));
    st.insert(resi(resi(a,b),c));
    st.insert(resi(resi(b,a),c));
    st.insert(resi(resi(c,a),b));
    st.insert(resi(resi(a,c),b));
    st.insert(resi(resi(b,c),a));
    st.insert(resi(resi(c,b),a));
    vector<string>vec;
    for(auto X : st) vec.push_back(X);
    int K = vec.size();
    vector<hes>niz(K);
    for(int i = 0; i < K; i++) {
        niz[i].build(vec[i],n);
    }
    int Q;
    cin >> Q;
    string str;
    cin >> str;
    str = '.' + str;
    hes T;
    T.build(str,n);
    for(int i = 1; i <= n; i++) modify(1,1,n,i,i,str[i]);
    bool ok = false;
    for(int i = 0; i < K; i++) {
        if(niz[i].val[n] == get(1,1,n,1,n)) ok = true;
    }
    cout << (ok ? "Yes\n" : "No\n");
    while(Q--) {
        int l,r;
        char c;
        cin >> l >> r >> c;
        modify(1,1,n,l,r,c);
        bool ok = false;
        for(int i = 0; i < K; i++) {
            if(niz[i].val[n] == get(1,1,n,1,n)) ok = true;
        }
        cout << (ok ? "Yes\n" : "No\n");
    }
}
/*
JOJO
JJOI
OJOO

a ^ b
a ^ c
b ^ c

a ^ a ^ b = b
a ^ a ^ c = c
a ^ b ^ c novo

b ^ a ^ b = a
b ^ a ^ c =
*/

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