Submission #810841

#	Time	Username	Problem	Language	Result	Execution time	Memory
810841		winter0101	Crossing (JOI21_crossing)	C++14	100 / 100	388 ms	17632 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
#define pll pair<long long,long long>
#define eb emplace_back
const long long du=1e9+7;
const long long base=311;
const int maxn=2e5+9;
int en(char r1){
if (r1=='J')return 1;
if (r1=='O')return 2;
return 3;
}
char b[4];
char conv(char p,char q){
if (p==q)return p;
bool pk[4];
memset(pk,0,sizeof(pk));
pk[en(p)]=1,pk[en(q)]=1;
for1(i,1,3){
if (pk[i])continue;
return b[i];
}
}
int n;
long long pw[maxn],st[maxn*4],lazy[maxn*4],dd[maxn];
void merge(int id,int l,int r){
int mid=(l+r)/2;
st[id]=(st[id*2]*pw[r-mid]+st[id*2+1])%du;
}
void push(int id,int l,int r){
if (lazy[id]){
    lazy[id*2]=lazy[id*2+1]=lazy[id];
    int rep=b[lazy[id]]-'A'+1;
    int mid=(l+r)/2;
    st[id*2]=(rep*dd[mid-l+1])%du;
    st[id*2+1]=(rep*dd[r-mid])%du;
    lazy[id]=0;
}
}
void update(int id,int l,int r,int u,int v,char val){
if (l>v||r<u||u>v)return;
if (u<=l&&r<=v){
    int rep=val-'A'+1;
    st[id]=(rep*dd[r-l+1])%du;
    lazy[id]=en(val);
    return;
}
push(id,l,r);
int mid=(l+r)/2;
update(id*2,l,mid,u,v,val);
update(id*2+1,mid+1,r,u,v,val);
merge(id,l,r);
}
string p,q,r;
vector<string>a;
void gen(){
    a.pb(p),a.pb(q),a.pb(r);
    map<string,bool>ck;
    ck[p]=1,ck[q]=1,ck[r]=1;
    while (true){
        bool fl=false;
        string nw="";
        for1(i,0,sz(a)-1){
        if (fl)break;
        for1(j,i+1,sz(a)-1){
        if (fl)break;
        for1(k,0,n-1){
        nw.pb(conv(a[i][k],a[j][k]));
        }
        if (!ck[nw]){
            ck[nw]=1;
            fl=true;
        }
        else nw="";
        }
        }
        if (!fl)break;
        a.pb(nw);
    }
}
vector<long long>has;
bool check(int vcl){
for (auto v:has)if (vcl==v)return true;
return false;
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    b[1]='J',b[2]='O',b[3]='I';
    cin>>n>>p>>q>>r;
    gen();
    vector<string>::iterator it=unique(all(a));
    a.resize(distance(a.begin(),it));
    for (auto v:a){
        long long s=0;
        for (auto u:v){
            s=(s*base+u-'A'+1)%du;
        }
        has.pb(s);
    }
    vector<string>().swap(a);
    pw[0]=1;
    for1(i,1,n)pw[i]=(pw[i-1]*base)%du;
    for1(i,1,n)dd[i]=(dd[i-1]*base+1)%du;
    int q;
    cin>>q;
    string t;
    cin>>t;
    t=" "+t;
    for1(i,1,n){
    update(1,1,n,i,i,t[i]);
    }
    if (check(st[1]))cout<<"Yes"<<'\n';
    else cout<<"No"<<'\n';
    for1(i,1,q){
    int l,r;
    char val;
    cin>>l>>r>>val;
    update(1,1,n,l,r,val);
    if (check(st[1]))cout<<"Yes"<<'\n';
    else cout<<"No"<<'\n';
    }

}

Compilation message (stderr)

Main.cpp: In function 'char conv(char, char)':
Main.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
   38 | }
      | ^

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