QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#534953#8338. Quad Kingdoms ChessliqingyangRE 0ms10740kbC++172.2kb2024-08-27 17:56:412024-08-27 17:56:41

Judging History

你现在查看的是最新测评结果

  • [2024-08-27 17:56:41]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:10740kb
  • [2024-08-27 17:56:41]
  • 提交

answer

#include<iostream>
#include<random>
#include<vector>
using namespace std;
mt19937 Rand(20080704);
int n,m,q,a[2][100010];
vector<pair<int,int> > e[2][100010];
unsigned int R[100010],ans[200010];
struct node
{
	int min1,min2,c;
	unsigned int v;
};
struct tree
{
	node a[400000];
	inline void update(int p)
	{
		a[p].min1=min(a[p<<1].min1,a[(p<<1)|1].min1);
		a[p].min2=min(a[p<<1].min1==a[p].min1?a[p<<1].min2:a[p<<1].min1
		,a[(p<<1)|1].min1==a[p].min1?a[(p<<1)|1].min2:a[(p<<1)|1].min1);
	}
	inline void change(int p,int minn,int c,unsigned int v)
	{
		if(a[p].min1>minn)
		{
			return;
		}
		a[p].min1=a[p].c=c;
		a[p].v^=v;
	}
	inline void pushdown(int p)
	{
		if(a[p].c)
		{
			change(p<<1,a[p].min1,a[p].c,a[p].v);
			change((p<<1)|1,a[p].min1,a[p].c,a[p].v);
			a[p].c=a[p].v=0;
		}
	}
	void change(int l,int r,int ll,int rr,int v,int p)
	{
		if(r<ll||l>rr||v<a[p].min1)
		{
			return;
		}
		if(ll<=l&&r<=rr&&v<a[p].min2)
		{
			change(p,a[p].min1,v,R[v]);
			return;
		}
		pushdown(p);
		int mid=l+r>>1;
		change(l,mid,ll,rr,v,p<<1);
		change(mid+1,r,ll,rr,v,(p<<1)|1);
		update(p);
	}
	void build(int l,int r,int p)
	{
		a[p].min1=0,a[p].min2=1e9;
		a[p].c=a[p].v=0;
		if(l==r)
		{
			return;
		}
		int mid=l+r>>1;
		build(l,mid,p<<1);
		build(mid+1,r,(p<<1)|1);
	}
	void query(int l,int r,int p)
	{
		if(l==r)
		{
			ans[l]^=a[p].v;
			return;
		}
		pushdown(p);
		int mid=l+r>>1;
		query(l,mid,p<<1);
		query(mid+1,r,(p<<1)|1);
	}
};
inline void solve(int n,int *a,vector<pair<int,int> > *e)
{
	static tree T;
	T.build(1,q,1);
	for(int i=n;i;i--)
	{
		int k=1,l=a[i];
		for(int j=0;j<e[i].size();j++)
		{
			int t=e[i][j].first;
			T.change(1,q,k,t-1,l,1);
			k=t,l=e[i][j].second;
		}
		T.change(1,q,k,q,l,1);
	}
	T.query(1,q,1);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[0][i];
	}
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>a[1][i];
	}
	cin>>q;
	for(int i=1,op,x,y;i<=q;i++)
	{
		cin>>op>>x>>y;
		e[op-1][x].push_back({i,y});
	}
	for(int i=1;i<=1e5;i++)
	{
		R[i]=Rand();
	}
	solve(n,a[0],e[0]);
	solve(m,a[1],e[1]);
	for(int i=1;i<=q;i++)
	{
		puts(ans[i]?"NO":"YES");
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 10740kb

input:

5
1 2 3 4 5
5
5 4 3 2 1
8
1 1 5
1 4 2
1 2 4
1 5 1
1 5 5
2 1 4
2 3 5
2 5 5

output:

NO
NO
NO
YES
NO
NO
NO
YES

result:

ok 8 tokens

Test #2:

score: -100
Runtime Error

input:

1
2
6
2 1 1 1 1 1
200000
2 6 2
1 1 1
1 1 1
1 1 2
2 1 1
1 1 2
1 1 1
2 4 1
2 1 2
1 1 1
1 1 2
2 5 1
1 1 1
1 1 2
1 1 1
2 6 1
1 1 2
1 1 2
1 1 2
2 3 1
1 1 1
2 1 1
2 6 2
1 1 2
2 4 1
1 1 2
2 6 1
1 1 2
1 1 1
2 5 2
2 6 2
1 1 1
2 4 2
2 5 2
2 6 2
1 1 1
2 5 1
2 6 2
1 1 2
1 1 1
1 1 1
2 4 1
1 1 2
1 1 2
1 1 2
2 3 2...

output:


result: