Submission #1239985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239985		trantrungkein	Crossing (JOI21_crossing)	C++20	26 / 100	7086 ms	6576 KiB

Main

// tất cả các TH có thể xảy ra từ việc lai 3 xâu là a^b,..., a^b^c, ..... thì ta kiểm tra xem có tồn tại không , sau đó dùng hash để cập nhật
#include <bits/stdc++.h>
#define int long long 
#define fi           first 
#define si           second 
#define For(i,a,b)   for (int i = (a), _b =(b); i <= _b; ++i)
#define all(v)       v.begin(), v.end()
#define Unique(v)    v.erase(unique(all(v)), v.end())   
#define MASK(i)      (1LL << (i))
#define bit(i,n)     (((n)>>(i)) & 1)
#define Vii          vector<pair<int,int>>
#define setpr(x)     cout<<setprecision(x)<<fixed
#define Prior        priority_queue< pair<int,int> , Vii, greater<Pair> >
using namespace std;
 
const int Mod = 1E9 + 7;
const long long INF  = 4E18;
const int N = 2e5 + 1, base = 31;

int Pow[N],n;
struct hes
{
    vector<int> hash;
    void Hash(string &s, int n)
    {   
       // cout << "F " << s << endl;
        hash.resize(n+3);
        For(i,1,n) hash[i] = (hash[i-1] + Pow[i]*(s[i]-'A'+1)%Mod)%Mod;
       // cout << hash[n] << endl;
    }
};
string cross(string a, string b)
{
    string s;
    s = s + ' ';
    For(i,1,n) s = s + 'J';
    for(int i = 1; i <= n; i++)
    {
        if(a[i] == b[i]) s[i] = a[i];
        else{
            bool J = 0, O = 0, I = 0;
            if(a[i] == 'J') J = 1;
            if(a[i] == 'O') O = 1;
            if(a[i] == 'I') I = 1;
            if(b[i] == 'J') J = 1;
            if(b[i] == 'O') O = 1;
            if(b[i] == 'I') I = 1;
            if(!J) s[i] = 'J';
            else if(!O) s[i] =  'O';
            else s[i] = 'I';
        } 
    }    
   // cout << s << endl;
    return s;
}
int st[4*N+1],Char[4*N],lazy[4*N],pre[N];
void Push(int id, int l, int r)
{
    if(!lazy[id]) return;
    st[id] = (Char[id] - 'A' + 1)*((pre[r] - pre[l-1] + Mod)%Mod)%Mod; 
    if(l != r)
    {
        lazy[2*id] = 1;
        lazy[2*id+1] = 1;
        Char[2*id] = Char[id];
        Char[2*id+1] = Char[id];
        lazy[id] = 0; 
    }
    lazy[id] = 0;
    return;
}
void update(int id, int l, int r, int tl, int tr, char c)
{   
    Push(id,l,r);
    if(l > tr || r < tl) return;
    if(tl <= l && r <= tr)
    {
        lazy[id] = 1;
        Char[id] = c;
        Push(id,l,r);
        return;
    }
    int mid = (l+r)/2;
    update(2*id,l,mid,tl,tr,c);
    update(2*id+1,mid+1,r,tl,tr,c);
    st[id] = (st[2*id+1] + st[2*id])%Mod;
}
unordered_map<int,bool> mp;
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //freopen("kein.inp","r",stdin);
    //freopen("kein.out","w",stdout);
    cin >> n;
    Pow[0] = 1;
    For(i,1,n) 
    {
        Pow[i] = Pow[i-1]*base%Mod;
        pre[i] = (pre[i-1] + Pow[i])%Mod;
    }
    string a,b,c;
    cin >> a >> b >> c;
    a = ' ' + a; b = ' ' + b; c = ' ' + c;
    set<string> TH;
    TH.insert(a);
    TH.insert(c);
    TH.insert(b);
    TH.insert(cross(a,b));
    TH.insert(cross(a,c));
    TH.insert(cross(c,b));
    TH.insert(cross(cross(a,b),c));
    TH.insert(cross(cross(a,c),b));
    TH.insert(cross(cross(b,c),a));
    int num = TH.size();
    vector<hes> check(num+1);
    int id = 0;
    for(string S : TH)
        {check[++id].Hash(S,n); mp[check[id].hash[n]] = 1;};
    string First;
     int q;
    cin >> q;
    cin >> First;
    First = ' ' + First;
    For(i,1,n) update(1,1,n,i,i,First[i]);
    bool ok = 0;
    //cout << st[1] << endl;
    For(i,1,num)
    {   
        if(check[i].hash[n] == st[1]) {
            ok = 1; break;
        }
    }
    cout << (ok ? "Yes" : "No") <<'\n';
   
    while(q--)
    {
        int l,r; char ci;
        cin >> l >> r >> ci;
        update(1,1,n,l,r,ci);
        bool ok = 0;
        //cout << st[1] << endl;
         if(mp.count(st[1])) {
            ok = 1; 
        }
        cout << (ok ? "Yes" : "No") <<'\n';
    }
}

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