Submission #167631

#TimeUsernameProblemLanguageResultExecution timeMemory
167631Atill83Tenis (COI19_tenis)C++14
7 / 100
71 ms7068 KiB
#include <bits/stdc++.h> #define ff first #define ss second #define endl '\n' using namespace std; const long long INF = (long long) 1e18; const int mod = (int) 1e9+7; const int MAXN = (int) 1e5+5; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; ll n, q; int a[MAXN], b[MAXN], c[MAXN]; ll yer1[MAXN], yer2[MAXN], yer3[MAXN], mx[MAXN]; pair<int, bool> t[4*MAXN]; void build(int v, int tl, int tr){ if(tl == tr){ t[v].ff = max(mx[a[tl]], max(mx[b[tl]], mx[c[tl]])); if(t[v].ff <= tl){ t[v].ss = 1; } }else{ int tm = (tl + tr) / 2; build(2*v, tl, tm); build(2*v + 1, tm + 1, tr); if(t[2*v].ss == 1){ t[v].ff = t[2*v].ff; t[v].ss = 1; }else if(t[2*v + 1].ss == 1){ if(t[2*v].ff <= t[2*v + 1].ff){ t[v].ff = t[2*v + 1].ff; t[v].ss = 1; }else{ t[v].ff = t[2*v].ff; t[v].ss = 0; } }else{ t[v].ff = max(t[2*v].ff, t[2*v + 1].ff); t[v].ss = 0; } } } void upd(int v, int tl , int tr, int pos){ if(tl == tr){ t[v].ff = max(mx[a[tl]], max(mx[b[tl]], mx[c[tl]])); if(t[v].ff <= tl){ t[v].ss = 1; }else{ t[v].ss = 0; } }else{ int tm = (tl + tr) / 2; if(pos <= tm) build(2*v, tl, tm); else build(2*v + 1, tm + 1, tr); //ll yeri = que(1, 1, n, ) if(t[2*v].ss == 1){ t[v].ff = t[2*v].ff; t[v].ss = 1; }else if(t[2*v + 1].ss == 1){ if(t[2*v].ff <= t[2*v + 1].ff){ t[v].ff = t[2*v + 1].ff; t[v].ss = 1; }else{ t[v].ff = t[2*v].ff; t[v].ss = 0; } }else{ t[v].ff = max(t[2*v].ff, t[2*v + 1].ff); t[v].ss = 0; } } } int que(int v, int tl, int tr, int l, int r){ if(l > r){ return 0; }else if(tl == l && tr == r){ return t[v].ff; }else{ int tm = (tl + tr)/ 2; ll ans1 = que(2*v, tl, tm, l, min(tm, r)), ans2 = que(2*v + 1, tm + 1, tr, max(tm + 1, l), r); return max(ans1, ans2); } } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); #ifdef Local freopen("../IO/int.txt","r",stdin); freopen("../IO/out.txt","w",stdout); #endif cin>>n>>q; for(int i = 1; i <= n; i++){ cin>>a[i]; yer1[a[i]] = i; } for(int i = 1; i <= n; i++){ cin>>b[i]; yer2[b[i]] = i; } for(int i = 1; i <= n; i++){ cin>>c[i]; yer3[c[i]] = i; mx[c[i]] = max(yer3[c[i]], max(yer2[c[i]], yer1[c[i]])); } bool deg = 0; build(1, 1, n); int yer; while(q--){ int type; cin>>type; if(type == 1){ int x; cin>>x; if(deg == 0){ deg = 1; yer = que(1, 1, n, 1, n); } //cout<<yer<<endl; cout<<(yer >= yer1[x] ? "DA" : "NE")<<endl; }else{ deg = 0; int court, l, r; cin>>court>>l>>r; if(court == 1){ swap(a[yer1[l]], a[yer1[r]]); swap(yer1[l], yer1[r]); ll cur1 = a[yer1[l]], cur2 = a[yer1[r]]; mx[cur1] = max(yer3[cur1], max(yer2[cur1], yer1[cur1])); mx[cur2] = max(yer3[cur2], max(yer2[cur2], yer1[cur2])); upd(1, 1, n, max(yer1[l], yer1[r])); upd(1, 1, n, min(yer1[l], yer1[r])); }else if(court == 2){ swap(b[yer2[l]], b[yer2[r]]); swap(yer2[l], yer2[r]); ll cur1 = b[yer2[l]], cur2 = b[yer2[r]]; mx[cur1] = max(yer3[cur1], max(yer2[cur1], yer1[cur1])); mx[cur2] = max(yer3[cur2], max(yer2[cur2], yer1[cur2])); upd(1, 1, n, max(yer2[l], yer2[r])); upd(1, 1, n, min(yer2[l], yer2[r])); }else{ swap(c[yer3[l]], c[yer3[r]]); swap(yer3[l], yer3[r]); ll cur1 = c[yer3[l]], cur2 = c[yer3[r]]; mx[cur1] = max(yer3[cur1], max(yer2[cur1], yer1[cur1])); mx[cur2] = max(yer3[cur2], max(yer2[cur2], yer1[cur2])); upd(1, 1, n, max(yer3[l], yer3[r])); upd(1, 1, n, min(yer3[l], yer3[r])); } } } #ifdef Local cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds "; #endif }
#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...