Submission #1118670

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118670		vjudge1	Tenis (COI19_tenis)	C++17	100 / 100	131 ms	7240 KiB

tenis

#include<bits/stdc++.h>
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=1e5+5;
int n,m,a[4][N];
namespace SGT
{
	int a[N<<2],p[N<<2],lt[N<<2];
	inline void pushup(int w){int o=(a[w<<1]>a[w<<1|1]);a[w]=a[w<<1|o],p[w]=p[w<<1|o];}
	inline void upd(int w,int x){a[w]+=x;lt[w]+=x;}
	inline void pushdown(int w){int &t=lt[w];if(t) upd(w<<1,t),upd(w<<1|1,t),t=0;}
	void updata(int x,int L,int R=n,int l=1,int r=n,int w=1)
	{
		if(L<=l&&r<=R) return upd(w,x);
		int mid=(l+r)>>1;pushdown(w);
		if(L<=mid) updata(x,L,R,l,mid,w<<1);
		if(mid<R) updata(x,L,R,mid+1,r,w<<1|1);
		pushup(w);
	}
	inline int ask(){return p[1];}
	void build(int l=1,int r=n,int w=1)
	{
		if(l==r) return a[w]=p[w]=l,void();
		int mid=(l+r)>>1;build(l,mid,w<<1);build(mid+1,r,w<<1|1);
		pushup(w);
	}
}
inline int MX(int i){return max({a[1][i],a[2][i],a[3][i]});}
inline void upd(int i,int x){SGT::updata(-x,MX(i));}
int main()
{
	// fr(tennis)
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;
	for(int o=1;o<=3;o++) for(int i=1,x;i<=n;i++) cin>>x,a[o][x]=i;
	SGT::build();
	for(int i=1;i<=n;i++) upd(i,1);
	for(int o,p,x,y;m--;)
	{
		cin>>o;
		if(o==1) cin>>x,cout<<(MX(x)<=SGT::ask()?"DA\n":"NE\n");
		else
		{
			cin>>p>>x>>y;if(x==y) continue;
			upd(x,-1),upd(y,-1),swap(a[p][x],a[p][y]),upd(x,1),upd(y,1);
		}
	}
	return 0;
}

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