Submission #881464

#	Time	Username	Problem	Language	Result	Execution time	Memory
881464		Iliya_	Crossing (JOI21_crossing)	C++14	100 / 100	363 ms	24092 KiB

Main

//IN THE NAME OF GOD
#include<bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
#define endl        '\n'
#define F           first
#define S           second
#define pii         pair<int,int>
#define all(x)      x.begin(),x.end()
#define pb          push_back
#define fastio      ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll; 
typedef long double dll;

#define int long long
const int N = 2e5+7, mod = 1e9+7, base = 73;
string a[3], t;  
set<int> s; 
int n, pw[N], seg[N<<2], dp[N];
pair<int,char> lz[N<<2];

int hashing(string s){
     int ans = 0;
     for(int i=0; i<ll(s.size()); i++) ans = ans * base % mod + (s[i]-'A'+1);
     return ans; 
}

string merge(string a, string b){
     string make = "";
     for(int i=0; i<ll(a.size()); i++){
          if (a[i] == b[i]) make += a[i]; 
          else{
               if ((a[i] == 'O' && b[i] == 'J') || (a[i] == 'J' && b[i] == 'O')) make+='I';
               if ((a[i] == 'O' && b[i] == 'I') || (a[i] == 'I' && b[i] == 'O')) make+='J';
               if ((a[i] == 'I' && b[i] == 'J') || (a[i] == 'J' && b[i] == 'I')) make+='O';
          }
     }
     return make;   
}

void build(int ind, int l, int r){ 
     if (l == r){
          int ans = 0; 
          for(int i=l; i<=r; i++) ans = (ans + (t[i]-'A'+1) * pw[n-1-i] % mod) % mod;
          seg[ind] = ans;
          return; 
     }
     int mid = (l+r)>>1;
     build(2*ind,l,mid);
     build(2*ind+1,mid+1,r); 
     seg[ind] += (seg[2*ind] + seg[2*ind+1]) % mod;
}

void shift(int ind, int l, int r){
     if (!lz[ind].F) return;
     int en = n-l-1, st = n-1-r; 
     int maj = dp[en] - (st == 0 ? 0 : dp[st-1]) + mod; 
     maj %= mod; 
     seg[ind] = (lz[ind].S-'A'+1) * maj % mod; 
     if (l != r){
          lz[2*ind] = lz[ind]; 
          lz[2*ind+1] = lz[ind]; 
     }
     lz[ind].F = 0;
}

void upd(int ind, int l, int r, int st, int en, char c){
     shift(ind,l,r);
     if (l > en || st > r) return; 
     if (l == r || (l >= st && r <= en)){
          int en = n-l-1, st = n-1-r; 
          int maj = dp[en] - (st == 0 ? 0 : dp[st-1]) + mod; 
          maj %= mod; 
          seg[ind] = (c-'A'+1) * maj % mod; 
          if (l != r){
               lz[2*ind] = {1,c}; 
               lz[2*ind+1] = {1,c}; 
          }
          return;
     }
     int mid = (l+r)>>1;
     upd(2*ind,l,mid,st,en,c);
     upd(2*ind+1,mid+1,r,st,en,c); 
     seg[ind] = (seg[2*ind]+seg[2*ind+1])%mod;
}

int32_t main(){
     fastio;

     pw[0] = dp[0] = 1;
     for(int i=1; i<N; i++){
          pw[i] = pw[i-1] * base % mod; 
          dp[i] = (dp[i-1] + pw[i]) % mod; 
     }
     cin >> n; 
     cin >> a[0] >> a[1] >> a[2];  
     s.insert(hashing(a[0])); 
     s.insert(hashing(a[1])); 
     s.insert(hashing(a[2]));
     for(int i=0; i<3; i++)for(int j=0; j<3; j++) if (i != j) s.insert(hashing(merge(a[i],a[j]))); 
     for(int i=0; i<3; i++){
          for(int j=0; j<3; j++){
               if (i == j) continue; 
               for(int k =0; k<3; k++){
                    if (k == i || k == j) continue; 
                    s.insert(hashing(merge(merge(a[i],a[j]),a[k])));
               }
          }
     }
     int q; cin >> q; 
     cin >> t; 
     build(1,0,n-1); 
     if (s.find(seg[1]) != s.end()) cout << "Yes" << endl; 
     else cout << "No" << endl;
     while(q--){
          int l,r; cin >> l >> r; l--; r--;
          char c; cin >> c; 
          upd(1,0,n-1,l,r,c); 
          if (s.find(seg[1]) != s.end()) cout << "Yes" << endl; 
          else cout << "No" << endl;
     }

     return 0;
}

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