Submission #144197

#TimeUsernameProblemLanguageResultExecution timeMemory
144197AbelyanTenis (COI19_tenis)C++17
0 / 100
664 ms17044 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]; int n,q,qan; set<int> s[3],tarb[3][3]; set<int>::iterator it; void ins(int ham,int val){ s[ham].insert(val); FOR(i,3){ if (ham==i)continue; it=tarb[i][ham].find(val); if (it==tarb[i][ham].end()){ tarb[ham][i].insert(val); qan++; } else{ tarb[i][ham].erase(it); qan--; } } } int get(){ int pat=-1; qan=0; FOR(i,n-1){ //cout<<a[0][i]<<" "<<a[1][i]<<" "<<a[2][i]<<endl; ins(0,a[0][i]); ins(1,a[1][i]); ins(2,a[2][i]); //cout<<qan<<" "; if (!qan)pat=i; } //cout<<endl; FOR(i,3){ s[i].clear(); FOR(j,3){ tarb[i][j].clear(); } } 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...