Submission #1187035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187035		_rain_	Tenis (COI19_tenis)	C++20	0 / 100	60 ms	3396 KiB

tenis

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

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

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

void build(int id,int l,int r){

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

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

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<=n;++i){
		int x; cin>>x;
		a[1][x]=i;
	}
	for(int i=1;i<=n;++i){
		int x; cin>>x;
		a[2][x]=i;
	}
	for(int i=1;i<=n;++i){
		int x; cin>>x;
		a[3][x]=i;
	}
	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]});
			int res=query(1,1,n);
			if (mx<=res){
				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: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 21
• Subtask 5: 0 / 49