代码求调
查看原帖
代码求调
713562
hahaxiang楼主2024/1/24 12:33

wa on test 4 436th token

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int T,n,m,a[N],b[N],d[N];
struct line{
	int l,r;
}c[N];
struct TREE{
	int tag,mx;
}tree[N*4];
bool cmp(line x,line y)
{
	return x.l<y.l;
}
int lson(int l,int r)
{
	return (l+r)/2;
}
int rson(int l,int r)
{
	return (l+r)/2+1;
}
void update(int x)
{
	tree[x].mx=max(tree[x*2].mx,tree[x*2+1].mx);
	return;
}
void pushdown(int x)
{
	if(tree[x].tag==-1)
	return;
	tree[x*2].tag=tree[x].tag;
	tree[x*2].mx=tree[x].tag;
	tree[x*2+1].tag=tree[x].tag;
	tree[x*2+1].mx=tree[x].tag;
	tree[x].tag=-1;
	return;
}
void build(int l,int r,int x)
{
	tree[x].tag=-1;
	if(l==r)
	{
		tree[x].mx=d[l];
		return;
	}
	build(l,lson(l,r),x*2);
	build(rson(l,r),r,x*2+1);
	update(x);
	return;
}
void change(int l,int r,int x,int l1,int r1)
{
	if(l>=l1&&r<=r1)
	{
		tree[x].tag=0;
		tree[x].mx=0;
		return;
	}
	pushdown(x);
	if(lson(l,r)>=l1)
	change(l,lson(l,r),x*2,l1,r1);
	if(rson(l,r)<=r1)
	change(rson(l,r),r,x*2+1,l1,r1);
	update(x);
	return;
}
int get(int l,int r,int x,int to)
{
	if(l==r)
	return tree[x].mx;
	pushdown(x);
	if(lson(l,r)>=to)
	return get(l,lson(l,r),x*2,to);
	else
	return get(rson(l,r),r,x*2+1,to);
	update(x);
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			a[i]=a[i-1]+a[i];
		}
		for(int i=1;i<=n;i++)
		{
			cin>>b[i];
			b[i]=b[i-1]+b[i];
		}
		for(int i=1;i<=n;i++)
		{
			if(a[i]!=b[i])
			d[i]=1;
			else
			d[i]=0;
		}
		build(1,n,1);
		for(int i=1;i<=m;i++)
		{
			cin>>c[i].l>>c[i].r;
		}
		sort(c+1,c+1+m,cmp);
		int z=0;
		bool fl=0;
		for(int i=1;i<=n;i++)
		{
			while(z!=m&&c[z+1].l<=i)
			{
				z++;
				if(get(1,n,1,c[z].r)==0)
				{
					change(1,n,1,c[z].l,c[z].r);
				}
			}
			if(get(1,n,1,i)==1)
			{
				fl=1;
				break;
			}
		}
		if(fl==1)
		cout<<"NO"<<'\n';
		else
		cout<<"YES"<<'\n';
	}
	return 0;
}
//1 6 10 12 15
//3 5 10 14 15
/*
1
5 4
1 2 3 4 5
1 2 3 4 5
1 4
2 4
3 4
4 4
*/
2024/1/24 12:33
加载中...