제출 #430442

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
430442		2fat2code	Crossing (JOI21_crossing)	C++17	26 / 100	6342 ms	14308 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define fr first
#define sc second
#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int nmax = 200005;
const int mod = 1e9 + 9;
const int p = 41;

int n, q, pw[nmax], tree[4*nmax], lazy[4*nmax], sump[nmax];
string Sa, Sb, Sc, T0;

map<int,int>mp;

int generatehash(string aux){
    int hsh = 0;
    for(int i=0;i<(int)aux.size();i++){
        hsh = (hsh + pw[i] * (aux[i] - '0') % mod) % mod;
    }
    return hsh;
}

vector<pair<string, int>>vecc;

void calc(){
    for(auto it : vecc){
        mp[it.sc] = 1;
    }
    for(int i=0;i<(int)vecc.size();i++){
        for(int j=0;j<i;j++){
            string aux;
            for(int t=0;t<n;t++){
                if(vecc[i].fr[t] == vecc[j].fr[t]){
                    aux += vecc[i].fr[t];
                }
                else if(vecc[i].fr[t] != '1' && vecc[j].fr[t] != '1'){
                    aux += '1';
                }
                else if(vecc[i].fr[t] != '0' && vecc[j].fr[t] != '0'){
                    aux += '0';
                }
                else{
                    aux += '2';
                }
            }
            int curr = generatehash(aux);
            if(mp.count(curr) == 0){
                mp[curr] = 1;
                vecc.push_back({aux, curr});
            }
        }
    }
}

void build(int l, int r, int nod){
    if(l == r){
        tree[nod] = (T0[l - 1] - '0');
    }
    else{
        int mid = l + (r - l) / 2;
        build(l, mid, 2*nod);
        build(mid+1, r, 2*nod+1);
        tree[nod] = (tree[2*nod] + pw[(mid - l + 1)] * tree[2*nod + 1] % mod) % mod;
    }
}

void push(int l, int r, int nod){
    if(lazy[nod] >= 1){
        tree[nod] = (lazy[nod] - 1LL) * sump[r - l];
        if(l != r){
            lazy[2*nod] = lazy[nod];
            lazy[2*nod+1] = lazy[nod];
        }
        lazy[nod] = 0;
    }
}

void update(int l, int r, int le, int ri, int val, int nod){
    push(l, r, nod);
    if(l > ri || r < le){
        return;
    }
    else if(l >= le && r <= ri){
        lazy[nod] = val;
        push(l, r, nod);
    }
    else{
        int mid = l + (r - l) / 2;
        update(l, mid, le, ri, val, 2*nod);
        update(mid + 1, r, le, ri, val, 2*nod + 1);
        tree[nod] = (tree[2*nod] + pw[(mid - l + 1)] * tree[2*nod + 1] % mod) % mod;
    }
}

bool check(){
    push(1, n, 1);
    for(auto it : vecc){
        if(it.sc == tree[1]){
            return true;
        }
    }
    return false;
}


int32_t main(){
    //ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
  //  freopen("input.in", "r", stdin);
    pw[0] = 1;
    sump[0] = 1;
    for(int i=1;i<nmax;i++){
        pw[i] = pw[i-1] * p % mod;
        sump[i] = (sump[i-1] + pw[i]) % mod;
    }
    cin >> n >> Sa >> Sb >> Sc >> q >> T0;
    for(auto &it : Sa){
        if(it == 'J') it = '0';
        else if(it == 'O') it = '1';
        else it = '2';
    }
    for(auto &it : Sb){
        if(it == 'J') it = '0';
        else if(it == 'O') it = '1';
        else it = '2';
    }
    for(auto &it : Sc){
        if(it == 'J') it = '0';
        else if(it == 'O') it = '1';
        else it = '2';
    }
    for(auto &it : T0){
        if(it == 'J') it = '0';
        else if(it == 'O') it = '1';
        else it = '2';
    }
    vecc.push_back({Sa, generatehash(Sa)});
    vecc.push_back({Sb, generatehash(Sb)});
    vecc.push_back({Sc, generatehash(Sc)});
    calc();
    build(1, n, 1);
    cout << (check() == true ? "Yes" : "No") << '\n';
    for(int i=1;i<=q;i++){
        int l, r;
        char c;
        cin >> l >> r >> c;
        int val;
        if(c == 'J') val = 1;
        else if(c == 'O') val = 2;
        else val = 3;
        update(1, n, l, r, val, 1);
        cout << (check() == true ? "Yes" : "No") << '\n';
    }
}

// 1. Solve the problem
// 2. ???
// 3. Profit

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