#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define D(x) cerr << #x << " is " << (x) << "\n";
#define ld long double
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const deque<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T,greater<T> >& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T,greater<T> >& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
const int N=1e5+5;
vector<vector<int> > arr(3,vector<int>(N)),pos(3,vector<int>(N)),last(3,vector<int>(N)),vals(3,vector<int>(N,-1));
vector<vector<tuple<int,int,int> > > dodaj(4*N);
void add(int qs,int qe,tuple<int,int,int> x,int l=0,int r=N-1,int i=1){
/*if(i==1)
printf("%i-%i %i %i %i\n",qs,qe,get<0>(x),get<1>(x),get<2>(x));*/
if(qs>r||qe<l)
return;
if(qs<=l&&qe>=r){
dodaj[i].pb(x);
return;
}
int m=(l+r)>>1;
add(qs,qe,x,l,m,2*i);
add(qs,qe,x,m+1,r,2*i+1);
}
int tr=0;
vector<int> queries(N);
set<int> intervals;
vector<vector<pair<int,int> > > undo;
vector<pair<int,int> > em;
void sett(int p,int a,int ind){
//printf("%i %i %i\n",p,a,ind);
vals[p][a]=ind;
undo.pb(em);
undo.back().pb({p,a});
if(vals[0][a]!=-1&&vals[1][a]!=-1&&vals[2][a]!=-1){
int mi=min({vals[0][a],vals[1][a],vals[2][a]}),ma=max({vals[0][a],vals[1][a],vals[2][a]});
//printf("%i: %i %i!!\n",a,mi,ma);
auto it=intervals.upper_bound(mi);
while(it!=intervals.end()&&(*it)<=ma)
undo.back().pb({-1,*it}),intervals.erase(it),it=intervals.upper_bound(mi);
}
}
void undo_it(){
for(auto p:undo.back())
if(p.f==-1)
intervals.insert(p.s);
else
vals[p.f][p.s]=-1;
undo.pop_back();
}
void solve(int l=0,int r=N-1,int i=1){
if(l>=tr)
return;
//printf("%i-%i!!\n",l,r);
for(auto p:dodaj[i])
sett(get<0>(p),get<1>(p),get<2>(p));
if(l==r){
int index=vals[0][queries[l]];
//cout << intervals << endl;
auto tr=*intervals.begin();
if(index<tr)
printf("DA\n");
else
printf("NE\n");
for(auto p:dodaj[i])
undo_it();
return;
}
int m=(l+r)>>1;
solve(l,m,2*i);
solve(m+1,r,2*i+1);
for(auto p:dodaj[i])
undo_it();
}
int main()
{
freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n,q;
scanf("%i %i",&n,&q);
for(int i=0;i<3;i++)
for(int j=0;j<n;j++)
scanf("%i",&arr[i][j]),arr[i][j]--,pos[i][arr[i][j]]=j;
for(int i=0;i<q;i++){
int t;
scanf("%i",&t);
if(t==1){
int x;
scanf("%i",&x);
queries[tr++]=x-1;
}else{
int p,a,b;
scanf("%i %i %i",&p,&a,&b);
p--;a--;b--;
if(last[p][a]!=tr)
add(last[p][a],tr-1,make_tuple(p,a,pos[p][a]));
if(last[p][b]!=tr)
add(last[p][b],tr-1,make_tuple(p,b,pos[p][b]));
last[p][b]=last[p][a]=tr;
swap(arr[p][pos[p][a]],arr[p][pos[p][b]]);
swap(pos[p][a],pos[p][b]);
}
}
for(int i=0;i<3;i++)
for(int j=0;j<n;j++)
if(last[i][j]!=tr)
add(last[i][j],tr-1,make_tuple(i,j,pos[i][j]));
for(int i=1;i<=n;i++)
intervals.insert(i);
solve();
return 0;
}
Compilation message
tenis.cpp: In function 'void solve(int, int, int)':
tenis.cpp:87:18: warning: variable 'p' set but not used [-Wunused-but-set-variable]
for(auto p:dodaj[i])
^
tenis.cpp:94:14: warning: variable 'p' set but not used [-Wunused-but-set-variable]
for(auto p:dodaj[i])
^
tenis.cpp: In function 'int main()':
tenis.cpp:99:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("in.txt","r",stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~
tenis.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i",&n,&q);
~~~~~^~~~~~~~~~~~~~~
tenis.cpp:105:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&arr[i][j]),arr[i][j]--,pos[i][arr[i][j]]=j;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
tenis.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&t);
~~~~~^~~~~~~~~
tenis.cpp:111:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&x);
~~~~~^~~~~~~~~
tenis.cpp:115:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i %i",&p,&a,&b);
~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
33 ms |
29808 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
33 ms |
29808 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
33 ms |
29808 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
34 ms |
29820 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
33 ms |
29808 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
