Submission #144206

#TimeUsernameProblemLanguageResultExecution timeMemory
144206AbelyanTenis (COI19_tenis)C++17
51 / 100
1073 ms3500 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; #define FOR(i,a) for (int i=0;i<(a);++i) #define FORD(i,a) for (int i=(a)-1;i>=0;i--) #define FORT(i,a,b) for (int i=(a);i<=(b);++i) #define FORTD(i,b,a) for (int i=(b);i>=(a);--i) #define trav(i,v) for (auto i : v) #define all(v) v.begin(),v.end() #define ad push_back #define fr first #define sc second #define mpr(a,b) make_pair(a,b) #define pir pair<int,int> #define all(v) v.begin(),v.end() #define make_unique(v) v.erase(unique(all(v)),v.end()) #define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) #define y1 EsiHancagorcRepa const int N=1e5+10; const ll MOD2=998244353; const ll MOD=1e9+7; void yes(){ cout<<"DA"<<endl; } void no(){ cout<<"NE"<<endl; } /* struct node{ set<int> s[3],tarb[3][3]; int qan; node(){qan=0;} }; set<int>::iterator it; node sg[4*N]; void ad(int v,int tl,int tr,int ind,int ham,int val){ sg[v].s[ham].insert(val); FOR(i,3){ if (ham==i)continue; it=sg[v].tarb[i][ham].find(val); if (it==sg[v].tarb[i][ham].end()){ sg[v].tarb[ham][i].insert(val); sg[v].qan++; } else{ sg[v].tarb[i][ham].erase(it); sg[v].qan--; } } if (tl==tr)return; int tm=(tl+tr)/2; if (ind<=tm)ad(v+v,tl,tm,ind,ham,val); else ad(v+v+1,tm+1,tr,ind,ham,val); } void rem(int v,int tl,int tr,int ind,int ham,int val){ sg[v].s[ham].erase(val); FOR(i,3){ if (ham==i)continue; it=sg[v].tarb[ham][i].find(val); if (it!=sg[v].tarb[ham][i].end()){ sg[v].tarb[ham][i].erase(it); sg[v].qan--; } else{ sg[v].tarb[i][ham].insert(val); sg[v].qan++; } } if (tl==tr)return; int tm=(tl+tr)/2; if (ind<=tm)rem(v+v,tl,tm,ind,ham,val); else rem(v+v+1,tm+1,tr,ind,ham,val); } int n,q; int query(int v,int tl,int tr){ if (sg[v].qan==0 && tr!=n-1) return tr-tl+1; if (tl==tr)return -1; int tm=(tl+tr)/2; int ans=query(v+v,tl,tm); if (query(v+v,tl,tm)==tm-tl+1){ return tm-tl+1+query(v+v+1,tm+1,tr); } return ans; } */ int a[3][N],ind[3][N],col[N]; int n,q,qan; int get(){ int pat=-1; qan=0; FOR(i,n-1){ //cout<<a[0][i]<<" "<<a[1][i]<<" "<<a[2][i]<<endl; col[a[0][i]]++; if (col[a[0][i]]==1 )qan++; if (col[a[0][i]]==3)qan--; col[a[1][i]]++; if (col[a[1][i]]==1)qan++; if (col[a[1][i]]==3)qan--; col[a[2][i]]++; if (col[a[2][i]]==1)qan++; if (col[a[2][i]]==3)qan--; //cout<<qan<<" "; if (!qan)pat=i; } FORT(i,1,n)col[i]=0; return pat; } int main(){ fastio; srng; cin>>n>>q; FOR(i,3) FORD(j,n){ cin>>a[i][j]; //ad(1,0,n-1,j,i,a[i][j]); ind[i][a[i][j]]=j; } int pat=get(); //cout<<pat<<endl; FOR(i,q){ int tp; cin>>tp; if (tp==1){ int x; cin>>x; //cout<<query(1,0,n-1)<<endl; if (ind[0][x]<=pat)no(); else yes(); } else{ int tp,v,u; cin>>tp>>v>>u; tp--; /* int indv=ind[tp][v]; int indu=ind[tp][u]; rem(1,0,n-1,indv,tp,v); ad(1,0,n-1,indv,tp,u); rem(1,0,n-1,indu,tp,u); ad(1,0,n-1,indu,tp,v); */ swap(ind[tp][v],ind[tp][u]); a[tp][ind[tp][v]]=v; a[tp][ind[tp][u]]=u; pat=get(); //cout<<pat<<endl; } } return 0; } /* 7 2 8 C 1 C 2 C 3 C 4 C 5 C 6 O 7 O 7 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...