Submission #1041742

#TimeUsernameProblemLanguageResultExecution timeMemory
1041742vjudge1Tenis (COI19_tenis)C++17
30 / 100
408 ms33792 KiB
#include<bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") using namespace std; #define int long long const int N = 100001; const int mod = 1e9+7; const int mod1 = 998244353; map<int,multiset<int>> g; vector<bool> vis(N); void dfs(int node){ if(vis[node])return; vis[node] = true; for(int child:g[node]){ dfs(child); } } void solve(){ int n,q;cin >> n>> q; int a[n+1][4]; for(int i = 1;i<=n ; i++) cin >> a[i][1]; for(int i = 1;i<=n ;i ++) cin >> a[i][2]; for(int i = 1;i<=n ;i ++) cin >> a[i][3]; vector<vector<int>> queries;bool f= true; for(int i = 0 ;i <q ;i ++){ int t;cin >> t; if(t == 1){ int x; cin >> x; queries.push_back({1,x}); } else{ int P,A,B; cin >> P >> A >> B;f=false; queries.push_back({2,P,A,B}); } } if(f){ //all queries are of type 1; map<int,int> m1; map<int,int> m2; map<int,int> m3; for(int i = 1;i<= n; i++){ m1[a[i][1]] = i; } for(int i = 1 ;i <=n ;i ++){ m2[a[i][2]] = i; } for(int i = 1;i<=n ;i ++){ m3[a[i][3]] = i; } vector<int> mx(n); for(int i = 1;i<=n ;i ++) for(int j = 1 ;j <=3 ;j ++) mx[a[i][j]-1] = max(mx[a[i][j]-1],i); int t[n+1][3][2]; t[n][0][0] = m2[a[n][1]]; t[n][0][1] = m3[a[n][1]]; t[n][1][0] = m1[a[n][2]]; t[n][1][1] = m3[a[n][2]]; t[n][2][0] = m1[a[n][3]]; t[n][2][1] = m2[a[n][3]]; for(int i = n-1;i>=1 ;i --){ t[i][0][0] = min(t[i-1][0][0],m2[a[i][1]]); t[i][0][1] = min(t[i-1][0][1],m3[a[i][1]]); t[i][1][0] = min(t[i-1][1][0],m1[a[i][2]]); t[i][1][1] = min(t[i-1][1][1],m3[a[i][2]]); t[i][2][0] = min(t[i-1][2][0],m1[a[i][3]]); t[i][2][1] = min(t[i-1][2][1],m2[a[i][3]]); } sort(mx.begin(),mx.end()); vector<bool> ans(n+1); for(int i = n;i>=1; i--){ int first = min(m1[a[i][1]],min(t[i][1][0],t[i][2][0])); int second = min({m2[a[i][1]],t[i][0][0],t[i][2][1]}); int third = min({m3[a[i][1]],t[i][0][1],t[i][1][1]}); if(mx[0]>=min({first,second,third})){ ans[a[i][1]] = true; } } for(int i = 0;i<q ;i ++){ int x = queries[i][1]; if(ans[x]){cout<<"DA"<<endl;} else cout<<"NE"<<endl; } } else{ for(int i = 2; i<=n ;i ++){ g[a[i-1][1]].insert(a[i][1]); g[a[i-1][2]].insert(a[i][2]); g[a[i-1][3]].insert(a[i][3]); } for(int its = 0 ;its <q ;its ++){ int it = queries[its][0]; if(it == 1){ int X = queries[its][1]; for(int i = 1;i<=n ;i++)vis[i] =false; dfs(X);bool f= true; for(int i = 1;i<=n ; i++){ if(!vis[i])f=false; } if(f)cout<<"DA"<<endl; else cout<<"NE"<<endl; } else{ int P = queries[its][1]; int A = queries[its][2]; int B = queries[its][3]; int first_pos = -1; int second_pos = -1; for(int i = 1;i<=n ;i ++){ if(a[i][P] == A)first_pos = i; if(a[i][P] == B)second_pos = i; } if(first_pos>1){ auto itt = g[a[first_pos-1][P]].find(a[first_pos][P]); if(itt!=g[a[first_pos-1][P]].end())g[a[first_pos-1][P]].erase(itt); } if(first_pos<n){ auto itt = g[a[first_pos][P]].find(a[first_pos+1][P]); if(itt!=g[a[first_pos][P]].end())g[a[first_pos][P]].erase(itt); } if(second_pos>1){ auto itt = g[a[second_pos-1][P]].find(a[second_pos][P]); if(itt!=g[a[second_pos-1][P]].end())g[a[second_pos-1][P]].erase(itt); } if(second_pos<n){ auto itt = g[a[second_pos][P]].find(a[second_pos+1][P]); if(itt!=g[a[second_pos][P]].end())g[a[second_pos][P]].erase(itt); } swap(a[first_pos][P],a[second_pos][P]); if(first_pos>1){ g[a[first_pos-1][P]].insert(a[first_pos][P]); } if(first_pos<n){ g[a[first_pos][P]].insert(a[first_pos+1][P]); } if(second_pos>1){ g[a[second_pos-1][P]].insert(a[second_pos][P]); } if(second_pos<n){ g[a[second_pos][P]].insert(a[second_pos+1][P]); } } } } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(NULL);cout.tie(NULL); int t=1; // cin>>t; cout<<setprecision(16); while(t--){ solve(); } }
#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...