This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define eb emplace_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
#define si(a) (ll)(a.size())
using namespace std;
#define maxn 100005
ll n,q;
array<ll,3> a[maxn];
ll c[maxn];
pll t[2*maxn];
ll lazy[2*maxn],ls[2*maxn],rs[2*maxn],tsz = 0,root = 0;
ll rev[3][maxn];
void f(ll i){c[i] = max({a[i][0],a[i][1],a[i][2]});}
void init(ll &v,ll tl,ll tr){
if(!v) v = ++tsz;
if(tl==tr){t[v] = {tl,tl};return;}
ll mid = (tl+tr)/2;
init(ls[v],tl,mid);
init(rs[v],mid+1,tr);
t[v] = min(t[ls[v]],t[rs[v]]);
}
void push(ll v){
t[v].fi+=lazy[v];
if(ls[v]) lazy[ls[v]]+=lazy[v];
if(rs[v]) lazy[rs[v]]+=lazy[v];
lazy[v] = 0;
}
void upd(ll v,ll tl,ll tr,ll l,ll r,ll x){
push(v);
if(l>r||l>tr||tl>r||tl>tr) return;
if(tl>=l&&tr<=r){lazy[v] = x;push(v);return;}
ll mid = (tl+tr)/2;
upd(ls[v],tl,mid,l,r,x);
upd(rs[v],mid+1,tr,l,r,x);
t[v] = min(t[ls[v]],t[rs[v]]);
}
void tc(){
cin >> n >> q;
for(ll e = 0;e<=2;e++) for(ll i = 1;i<=n;i++){
cin >> a[i][e];
rev[e][a[i][e]] = i;
}
for(ll e = 0;e<=2;e++) for(ll i = 1;i<=n;i++) a[i][e] = rev[e][i];
for(ll i = 1;i<=n;i++) f(i);
init(root,1,n);
for(ll i = 1;i<=n;i++){
upd(root,1,n,c[i],n,-1);
}
while(q--){
ll tip; cin >> tip;
if(tip==1){
ll i; cin >> i;
push(root);
ll x = t[root].sc;
if(x>=c[i]) cout<<"DA"<<endl;
else cout<<"NE"<<endl;
}else{
ll x,i,j;
cin >> x >> i >> j;
x--;
upd(root,1,n,c[j],n,1);
upd(root,1,n,c[i],n,1);
swap(a[i][x],a[j][x]);
f(i);
f(j);
upd(root,1,n,c[j],n,-1);
upd(root,1,n,c[i],n,-1);
}
}
}
int main(){
ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
int t; t = 1;
while(t--){
tc();
}
return (0-0);
}
/**
4 4
1 2 3 4
2 1 3 4
2 4 3 1
1 1
1 4
2 3 1 4
1 4
**/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |