Submission #1187047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187047		_rain_	Tenis (COI19_tenis)	C++20	100 / 100	126 ms	4972 KiB

tenis

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N=(int)1e6;
pair<int,int>st[N*4+2];
int lazy[N*4+2];
int a[4][N+2]={};
int n;

pair<int,int>compare(pair<int,int>&x,pair<int,int>&y){
	if (x.first>y.first) return y;
	
	return x;
}

#define lef(id) id*2
#define rig(id) id*2+1
void pushdown(int id){
	int&t=lazy[id];
	lazy[lef(id)]+=t,st[lef(id)].first+=t;
	lazy[rig(id)]+=t,st[rig(id)].first+=t;
	t=0;
	return ;
}

void build(int id,int l,int r){
	if (l>r) return;
	if (l==r) st[id]={l,l};
	else{
		int m=(l+r)/2;
		build(lef(id),l,m);
		build(rig(id),m+1,r);
		st[id]=compare(st[lef(id)],st[rig(id)]);
	}
}

void upd(int id,int l,int r,int u,int v,int val){
	if (l>v||r<u) return;
	if (u<=l&&r<=v){
		st[id].first+=val;
		lazy[id]+=val;
		return;
	}
	int m=(l+r)/2;
	pushdown(id);
	upd(lef(id),l,m,u,v,val);
	upd(rig(id),m+1,r,u,v,val);
	st[id]=compare(st[lef(id)],st[rig(id)]);
	return;
}

const int INF=(int)1e9+7;
pair<int,int>Get(int id,int l,int r,int u,int v){
	if (l>v||r<u) return {INF,INF};
	if (u<=l&&r<=v) return st[id];
	int m=(l+r)/2;
	pushdown(id);
	pair<int,int>g1=Get(lef(id),l,m,u,v),g2=Get(rig(id),m+1,r,u,v);
	return compare(g1,g2);
}

void modify(int x,int add){
	int mx=max({a[1][x],a[2][x],a[3][x]});
	upd(1,1,n,mx,n,add);
	return;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);

	int q;
	cin>>n>>q;
	for(int i=1;i<=3;++i){
		for(int j=1;j<=n;++j) {
			int x; cin>>x;
			a[i][x]=j;
		}
	}
	build(1,1,n);
	for(int i=1;i<=n;++i) modify(i,-1);
	while(q--){
		int t; cin>>t;
		if (t==1){
			int x; cin>>x;
			int mx=max({a[1][x],a[2][x],a[3][x]});
			if (mx<=(st[1].first==0?st[1].second:n)){
				cout<<"DA\n";
			}
			else cout<<"NE\n";
		}
		else{
			int p,A,B; cin>>p>>A>>B;
			modify(A,1);
			modify(B,1);
			swap(a[p][A],a[p][B]);
			modify(A,-1);
			modify(B,-1);
		}
	}
}

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