Submission #1221775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221775		ErJ	Crossing (JOI21_crossing)	C++20	26 / 100	7089 ms	71724 KiB

Main

#include <bits/stdc++.h>

#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define pp pair<ll, ll>


using namespace std;

vi inp(string a){
    vi A(a.size());
    for(int i = 0; i < a.size(); i++){
        if(a[i] == 'J'){
            A[i] = 0;
        }else if(a[i] == 'O'){
            A[i] = 1;
        }else if(a[i] == 'I'){
            A[i] = 2;
        }
    }
    return A;
}

vi add(vi a, vi b, vi c, vi d){
    ll n = a.size();
    vi ans(n);
    for(int i = 0; i < n; i++){
        ans[i] = (a[i] + b[i] + c[i] + d[i]) % 3;
    }
    return ans;
}

vi Itree, lazy;
vi ex;
ll mod = 1000000007;
ll p = 31;
ll inv = 1;

ll modpow(ll a, ll b, ll md){
    if(b == 0) return 1;
    if(b == 1) return a;
    ll ans = modpow(a, b / 2, md);
    if(b % 2 == 0){
        return ans * ans % md;
    } else{
        return (((ans * ans) % md) * a) % md;
    }
}

void init(ll n){
    ex.resize(n, 1);
    for(int i = 1; i < n; i++){
        ex[i] = (ex[i - 1] * p) % mod;
    }
    inv = modpow(p - 1, mod - 2, mod);
    while(n & (n - 1)) n++;
    Itree.resize(2*n, 0);
    lazy.resize(2*n, -1);
}

void setSum(ll u, ll a, ll b, ll val){
    Itree[u] = (((val * ex[a] % mod) * ((ex[b - a] - 1 + mod) % mod)) % mod) * inv % mod;
}

void lazyUpdate(ll u, ll a, ll b){
    if(lazy[u] == -1) return;
    setSum(u, a, b, lazy[u]);
    if(2*u < Itree.size()){
        lazy[2*u] = lazy[u];
        lazy[2*u + 1] = lazy[u];
    }
    lazy[u] = -1; 
}

void setRange2(ll u, ll l, ll r, ll a, ll b, ll val){
    lazyUpdate(u, a, b);
    if(l == a && r == b){
        lazy[u] = val;
        lazyUpdate(u, a, b);
        return;
    }
    ll s = (a + b) / 2;
    if(s >= r){
        setRange2(2*u, l, r, a, s, val);
    }else if(s <= l){
        setRange2(2*u + 1, l, r, s, b, val);
    }else{
        setRange2(2*u, l, s, a, s, val);
        setRange2(2*u + 1, s, r, s, b, val);
    }
    lazyUpdate(2*u, a, s);
    lazyUpdate(2*u + 1, s, b);
    Itree[u] = Itree[2*u] + Itree[2*u + 1] % mod;
}

void setRange(ll l, ll r, ll val){
    setRange2(1, l, r, 0, Itree.size() / 2, val);
}

ll countHash(vi A){
    ll ans = 0;
    for(int i = 0; i < A.size(); i++){
        ans += A[i] * ex[i];
        ans %= mod;
    }
    return ans;
}



int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll n;
    cin >> n;
    string a, b, c;
    cin >> a >> b >> c;
    vi A = inp(a), B = inp(b), C = inp(c);
    vvi poss = {A, B, C, add(A, A, B, B), add(A, A, C, C), add(B, B, C, C), add(A, B, C, A), add(A, B, C, B), add(A, B, C, C)};
    init(n);
    set<ll> hash;
    for(int i = 0; i < poss.size(); i++){
        hash.insert(countHash(poss[i]));
    }
    ll q;
    cin >> q;
    string t;
    cin >> t;
    vi T = inp(t);
    bool ok = false;
    for(int i = 0; i < poss.size(); i++){
        bool akt = true;
        for(int j = 0; j < poss[i].size(); j++){
            if(poss[i][j] != T[j]){
                akt = false;
            }
        }
        if(akt) ok = true;
    }
    if(ok) {
            cout << "Yes" << '\n';
    }else{
        cout << "No" << '\n';
    }
    /*for(int i = 0; i < n; i++){
        setRange(i, i + 1, T[i]);
    }
    if(hash.count(Itree[1])){
        cout << "Yes" << '\n';
    }else{
        cout << "No" << '\n';
    }*/
    while(q--){
        ll x, y, z;
        char ch;
        cin >> x >> y >> ch;
        if(ch == 'J'){
            z = 0;
        }else if(ch == 'O'){
            z = 1;
        }else if(ch == 'I'){
            z = 2;
        }
        for(int i = x - 1; i < y; i++){
            T[i] = z;
        }
        bool ok = false;
        for(int i = 0; i < poss.size(); i++){
            bool akt = true;
            for(int j = 0; j < poss[i].size(); j++){
                if(poss[i][j] != T[j]){
                    akt = false;
                }
            }
            if(akt) ok = true;
        }
        if(ok) {
             cout << "Yes" << '\n';
        }else{
            cout << "No" << '\n';
        }
        /*setRange(x - 1, y, z);
        if(hash.count(Itree[1])){
            cout << "Yes" << '\n';
        }else{
            cout << "No" << '\n';
        }*/
    }
}

/*

4
JOJO
JJOI
OJOO
3
IJOJ
1 4 O
2 2 J
2 4 I


3
JOI
JOI
JOI
2
OJI
1 2 O
1 1 J

*/

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