제출 #1186975

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1186975		_rain_	Tenis (COI19_tenis)	C++20	0 / 100	41 ms	3684 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&t=lazy[id];
	lazy[lef(id)]+=t,st[lef(id)]+=t;
	lazy[rig(id)]+=t,st[rig(id)]+=t;
	t=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){
	if (l>v||r<u) return;
	if (u<=l&&r<=v){
		st[id]+=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]=min(st[lef(id)],st[rig(id)]);
	return;
}
int query(int id,int l,int r){
	if (l==r) return l;
	pushdown(id);
	int m=(l+r)/2;
	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<=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]});
			int res=query(1,1,n);
			//cout<<res<<'\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