Submission #571487

#	Time	Username	Problem	Language	Result	Execution time	Memory
571487		Jasiekstrz	Tenis (COI19_tenis)	C++17	100 / 100	432 ms	6212 KiB

tenis

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e5;
const int P=1<<17;
int t[N+10][3];
int pot;
int tr[2*P+10];
int lazy[2*P+10];
void push_down(int x)
{
	for(int i:{2*x,2*x+1})
	{
		tr[i]+=lazy[x];
		lazy[i]+=lazy[x];
	}
	lazy[x]=0;
	return;
}
void add(int x,int l,int r,int ls,int rs,int c)
{
	if(ls>rs)
		swap(ls,rs);
	if(rs<=l || r<ls)
		return;
	if(ls<=l && r<rs)
	{
		tr[x]+=c;
		lazy[x]+=c;
		return;
	}
	push_down(x);
	int mid=(l+r)/2;
	add(2*x,l,mid,ls,rs,c);
	add(2*x+1,mid+1,r,ls,rs,c);
	tr[x]=min(tr[2*x],tr[2*x+1]);
	return;
}
int cut(int x)
{
	if(x>=pot)
		return x-pot+1;
	push_down(x);
	if(tr[2*x]==0)
		return cut(2*x);
	return cut(2*x+1);
}
void add_person(int x,int c)
{
	add(1,1,pot,t[x][0],t[x][1],c);
	add(1,1,pot,t[x][0],t[x][2],c);
	add(1,1,pot,t[x][1],t[x][2],c);
	return;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,q;
	cin>>n>>q;
	for(int j=0;j<3;j++)
	{
		for(int i=1;i<=n;i++)
		{
			int x;
			cin>>x;
			t[x][j]=i;
		}
	}
	for(pot=1;pot<n;pot*=2);
	for(int i=1;i<=n;i++)
		add_person(i,1);
	while(q--)
	{
		int ty;
		cin>>ty;
		if(ty==1)
		{
			int x;
			cin>>x;
			cout<<(t[x][0]<=cut(1) ? "DA":"NE")<<"\n";
		}
		else
		{
			int a,b,c;
			cin>>c>>a>>b;
			c--;
			add_person(a,-1);
			add_person(b,-1);
			swap(t[a][c],t[b][c]);
			add_person(a,1);
			add_person(b,1);
		}
	}
	return 0;
}

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