Submission #283770

#	Time	Username	Problem	Language	Result	Execution time	Memory
283770		AMO5	Tenis (COI19_tenis)	C++17	30 / 100	680 ms	22488 KiB

tenis

//koosaga's sol
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end()  
#define sz(x) int(x.size()) 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

const ll INF=63;
const int mxn=1e5+5;
bool DEBUG=0;

int n,q;
int a[3][mxn];
map<int,int>pos[3];

ll tree[mxn*4],lazy[mxn*4];

void puttag(int id, int v){
	tree[id]+=v;
	lazy[id]+=v;
	return;
}

void pushdown(int id, int le, int ri){
	ll x = lazy[id];
	lazy[id]=0ll;
	if(le==ri||x==0)return;
	puttag(id*2,x);
	puttag(id*2+1,x);
	return;
}

void pushup(int id, int le, int ri){
	tree[id]=min(tree[id*2],tree[id*2+1]);
	return;
}

void upd(int x, int y, int v, int id=1, int le=0, int ri=n-2){
	if(x>ri||le>y)return;
	if(x<=le&&ri<=y){
		puttag(id,v);
		return;
	}
	pushdown(id,le,ri);
	int mid=(le+ri)/2;
	upd(x,y,v,id*2,le,mid);
	upd(x,y,v,id*2+1,mid+1,ri);
	pushup(id,le,ri);
}

int query(int x, int y, int id=1, int le=0, int ri=n-2){
	if(x>ri||le>y)return 1e9;
	if(x<=le&&ri<=y){
		//cerr<<id<<" "<<le<<" "<<ri<<" : "<<tree[id]<<"\n";
		return tree[id];
	}
	pushdown(id,le,ri);
	int mid=(le+ri)/2;
	int left = query(x,y,id*2,le,mid);
	int right = query(x,y,id*2+1,mid+1,ri);
	return min(left,right);
}

void add(int x, int v){
	int mn = min({pos[0][x],pos[1][x],pos[2][x]});
	int mx = max({pos[0][x],pos[1][x],pos[2][x]});
	//cerr<<x<<": "<<mn<<" "<<mx-1<<" "<<v<<"\n";
	upd(mn,mx-1,v);
}

void run(int id=1, int le=0, int ri=n-2){
	cerr<<id<<" "<<le<<" "<<ri<<" "<<tree[id]<<" \n";
	if(le==ri)return;
	int mid=(le+ri)>>1;
	run(id*2,le,mid);
	run(id*2+1,mid+1,ri);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
    cin>>n>>q;
    for(int i=0; i<3; i++){
		for(int j=0; j<n; j++){
			cin>>a[i][j];
			a[i][j]--;
			pos[i][a[i][j]]=j;
		}
	}
	for(int i=0; i<n; i++){
		add(i,+1);
	}
	//run();
	while(q--){
		int typ;
		cin>>typ;
		if(typ==1){
			int x; cin>>x;
			x--;
			int mn = min({pos[0][x],pos[1][x],pos[2][x]});
			//cerr<<"checking 0 "<<mn-1<<"\n";
			cout<<(query(0,mn-1)?"DA":"NE")<<"\n";
		}else{
			int p,x,y;
			cin>>p>>x>>y;
			p--; x--; y--;
			add(x,-1); add(y,-1);
			int posx = pos[p][x];
			int posy = pos[p][y];
			swap(pos[p][x],pos[p][y]);
			add(x,+1); add(y,+1);
		}
		//run();
	}
}
	
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN

Compilation message (stderr)

tenis.cpp: In function 'int main()':
tenis.cpp:122:8: warning: unused variable 'posx' [-Wunused-variable]
  122 |    int posx = pos[p][x];
      |        ^~~~
tenis.cpp:123:8: warning: unused variable 'posy' [-Wunused-variable]
  123 |    int posy = pos[p][y];
      |        ^~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 0 / 21
• Subtask 5: 0 / 49