Submission #846809

#TimeUsernameProblemLanguageResultExecution timeMemory
846809AbitoCrossing (JOI21_crossing)C++17
100 / 100
1326 ms24376 KiB
#include <bits/stdc++.h> #define F first #define S second #define pb push_back #define ppb pop_back #define ep insert #define endl '\n' #define elif else if #define pow pwr #define sqrt sqrtt #define int long long #define y1 YONE typedef unsigned long long ull; using namespace std; struct que{ int l,r;char x; }; const int N=2e5+5; int n,seg[4*N+5],q,po[N],pj[N],pi[N]; char a[N],b[N],lazy[4*N+5]; set<string> s; que c[N]; bool ans[N]; string cross(string a,string b){ string c; for (int i=0;i<a.size();i++){ if (a[i]==b[i]){ c+=a[i];continue; }string v="JOI"; for (int j=0;j<3;j++){ if (v[j]==a[i] || v[j]==b[i]) continue; c+=v[j]; } }return c; } int build(int node,int l,int r){ lazy[node]='A'; if (l==r) return seg[node]=(a[l]==b[l]); int mid=(l+r)/2; return seg[node]=build(node*2,l,mid)+build(node*2+1,mid+1,r); } int edit(int node,int l,int r,int lx,int rx,char x){ if (r<lx || l>rx){ if (lazy[node]!='A'){ if (lazy[node]=='O') seg[node]=po[r]-po[l-1]; elif (lazy[node]=='J') seg[node]=pj[r]-pj[l-1]; else seg[node]=pi[r]-pi[l-1]; }return seg[node]; } if (l>=lx && r<=rx){ lazy[node]=x; if (lazy[node]=='O') seg[node]=po[r]-po[l-1]; elif (lazy[node]=='J') seg[node]=pj[r]-pj[l-1]; else seg[node]=pi[r]-pi[l-1]; return seg[node]; }int mid=(l+r)/2; if (lazy[node]!='A'){ lazy[node*2]=lazy[node]; lazy[node*2+1]=lazy[node]; lazy[node]='A'; }return seg[node]=edit(node*2,l,mid,lx,rx,x)+edit(node*2+1,mid+1,r,lx,rx,x); } int32_t main(){ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); cin>>n;string h;cin>>h,s.ep(h),cin>>h,s.ep(h),cin>>h,s.ep(h); while (true){ set<string> z; for (auto u:s){ for (auto v:s){ z.ep(cross(u,v)); } }bool ok=false; for (auto u:z){ if (s.count(u)) continue; ok=true; s.ep(u); }if (!ok) break; } cin>>q; for (int i=1;i<=n;i++) cin>>b[i]; for (int i=1;i<=q;i++) cin>>c[i].l>>c[i].r>>c[i].x; for (auto u:s){ for (int i=1;i<=n;i++){ a[i]=u[i-1]; po[i]=po[i-1],pj[i]=pj[i-1],pi[i]=pi[i-1]; if (a[i]=='J') pj[i]++; elif (a[i]=='O') po[i]++; else pi[i]++; } build(1,1,n); if (seg[1]==n) ans[0]|=1; for (int i=1;i<=q;i++){ edit(1,1,n,c[i].l,c[i].r,c[i].x); if (seg[1]==n) ans[i]|=1; } }for (int i=0;i<=q;i++){ if (ans[i]) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }

Compilation message (stderr)

Main.cpp: In function 'std::string cross(std::string, std::string)':
Main.cpp:26:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (int i=0;i<a.size();i++){
      |                  ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...