NOI批量评测 - 记录详情

#	状态分数	耗时	内存占用

#1	Accepted 4	2ms	500 KiB
#2	Accepted 4	2ms	404 KiB
#3	Accepted 4	2ms	404 KiB
#4	Accepted 4	3ms	404 KiB
#5	Accepted 4	2ms	404 KiB
#6	Accepted 4	3ms	408 KiB
#7	Accepted 4	3ms	468 KiB
#8	Accepted 4	33ms	908 KiB
#9	Accepted 4	22ms	908 KiB
#10	Accepted 4	41ms	904 KiB
#11	Accepted 4	40ms	912 KiB
#12	Accepted 4	861ms	14.9 MiB
#13	Accepted 4	795ms	14.9 MiB
#14	Accepted 4	1017ms	14.9 MiB
#15	Accepted 4	997ms	14.9 MiB
#16	Accepted 4	1105ms	14.9 MiB
#17	Accepted 4	1109ms	14.9 MiB
#18	Accepted 4	1122ms	14.9 MiB
#19	Time Exceeded 0	≥2703ms	≥30.5 MiB
#20	Time Exceeded 0	≥2703ms	≥30.5 MiB
#21	Time Exceeded 0	≥2702ms	≥30.5 MiB
#22	Time Exceeded 0	≥2702ms	≥30.5 MiB
#23	Time Exceeded 0	≥2702ms	≥30.5 MiB
#24	Time Exceeded 0	≥2702ms	≥30.5 MiB
#25	Time Exceeded 0	≥2702ms	≥30.6 MiB

#include<bits/stdc++.h>
using namespace std;
#define int long long

inline int read()
{
	int x=0,r=1;
	char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-') r=-1;
		ch=getchar();
	}
	while(isdigit(ch))
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*r;
}

int c,T;

int n;
struct node
{
	int a,b,t,num;
} d[200005];
int tag[800005];

struct seg
{
	int l,r,sum,nxtm,sum1;
	seg operator +(const seg b) const
	{
		seg ans;
		ans.l=l;
		ans.r=b.r;
		ans.sum=sum+b.sum;
		ans.sum1=sum1+b.sum1;
		ans.nxtm=nxtm+sum*(b.r-b.l+1)+b.nxtm;
		return ans;
	}
	seg set1()
	{
		seg ans;
		ans.l=l;
		ans.r=r;
		ans.sum=(r-l+1);
		ans.sum1=sum1;
		int d=(r-l+1);
		ans.nxtm=d*(d+1)/2;
		return ans;
	}
} tr[1000005];

void pushdown(int p,int l,int r)
{
	if(tag[p]==0) return;
	if(l==r)
	{
		tag[p]=0;
		return;
	}
	tr[p<<1]=tr[p<<1].set1();
	tr[p<<1|1]=tr[p<<1|1].set1();
	tag[p<<1]=1;
	tag[p<<1|1]=1;
	tag[p]=0;
}

void build(int p,int l,int r)
{
	if(l==r)
	{
		tag[p]=0;
		tr[p].l=l;
		tr[p].r=r;
		tr[p].sum=d[l].a-d[l-1].a;
		//if(l==2) cout<<p<<' '<<l<<' '<<tr[p].sum<<endl;
		//cout<<p<<' '<<tr[p].sum<<endl;
		tr[p].sum1=0;
		tr[p].nxtm=tr[p].sum;
		return;
	}
	tag[p]=0;
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	tr[p]=tr[p<<1]+tr[p<<1|1];
	//cout<<p<<' '<<l<<' '<<r<<' '<<tr[p].sum<<endl;
}

int cmp(node a,node b)
{
	if(a.t==b.t) return a.b<b.b;
	return a.t<b.t;
}

int pos(int p,int l,int r,int nr)
{
	//cout<<p<<' '<<l<<' '<<r<<' '<<nr<<' '<<tr[p].sum<<endl;
	if(nr==0) return 0;
	pushdown(p,l,r);
	if(r<=nr) return tr[p].sum;
	int mid=(l+r)>>1;
	int ans=pos(p<<1,l,mid,nr);
	if(mid+1<=nr) ans+=pos(p<<1|1,mid+1,r,nr);
	//cout<<p<<' '<<l<<' '<<r<<' '<<ans<<endl;
	return ans;
}

void stab(int p,int l,int r,int k)
{
	if(l==r)
	{
		tr[p].sum1=1;
		return;
	}
	pushdown(p,l,r);
	int mid=(l+r)>>1;
	if(mid>=k) stab(p<<1,l,mid,k);
	else stab(p<<1|1,mid+1,r,k);
	tr[p]=tr[p<<1]+tr[p<<1|1];
}

void update(int p,int l,int r,int k,int nu)
{
	if(l==r)
	{
		tr[p].sum=nu;
		tr[p].nxtm=nu;
		return;
	}
	pushdown(p,l,r);
	int mid=(l+r)>>1;
	if(mid>=k) update(p<<1,l,mid,k,nu);
	else update(p<<1|1,mid+1,r,k,nu);
	tr[p]=tr[p<<1]+tr[p<<1|1];
}

int check(int p,int l,int r,int nl,int nr)
{
	if(nl<=l&&nr>=r)
	{
		return tr[p].sum1;
	}
	pushdown(p,l,r);
	int mid=(l+r)>>1;
	int cnt=0;
	if(mid>=nl) cnt+=check(p<<1,l,mid,nl,nr);
	if(mid+1<=nr) cnt+=check(p<<1|1,mid+1,r,nl,nr);
	return cnt;
}

seg calc(int p,int l,int r,int nl,int nr)
{
	if(nl<=l&&nr>=r)
	{
		return tr[p];
	}
	seg ans;
	pushdown(p,l,r);
	int mid=(l+r)>>1;
	if(mid>=nl)
	{
		ans=calc(p<<1,l,mid,nl,nr);
		if(mid+1<=nr) ans=ans+calc(p<<1|1,mid+1,r,nl,nr);
		//cout<<p<<' '<<l<<' '<<r<<' '<<ans.l<<' '<<ans.r<<' '<<ans.nxtm<<endl;
		return ans;
	}
	if(mid+1<=nr) ans=calc(p<<1|1,mid+1,r,nl,nr);
	//cout<<p<<' '<<l<<' '<<r<<' '<<ans.l<<' '<<ans.r<<' '<<ans.nxtm<<endl;
	return ans;
}

void reset(int p,int l,int r,int nl,int nr)
{
	if(nl<=l&&nr>=r)
	{
		tr[p]=tr[p].set1();
		tag[p]=1;
		return;
	}
	pushdown(p,l,r);
	int mid=(l+r)>>1;
	if(mid>=nl) reset(p<<1,l,mid,nl,nr);
	if(mid+1<=nr) reset(p<<1|1,mid+1,r,nl,nr);
	tr[p]=tr[p<<1]+tr[p<<1|1];
}

void work()
{
	n=read();
	//int reu=0;
	for(int i=1;i<=n;i++)
	{
		d[i].a=read();
		//if(i>=1481&&i<=2978) reu+=d[i].a;
		d[i].b=read();
		d[i].t=read();
		d[i].num=i;
	}
	//cout<<reu<<endl;
	build(1,1,n);
	//calc(1,1,n,3,5);
	//pos(1,1,n,25);
	//
	//seg a1=calc(1,1,n,1,1);
	/*
	cout<<a1.sum<<' '<<a1.nxtm<<endl;
	seg a2=calc(1,1,n,2,2);
	cout<<a2.l<<' '<<a2.r<<' '<<a2.nxtm<<' '<<a2.sum<<endl;
	cout<<(calc(1,1,n,1,1)+calc(1,1,n,2,2)).nxtm<<endl;
	for(int i=1;i<=n;i++) cout<<calc(1,1,n,1,i).nxtm<<' ';
	cout<<endl;
	* */
	sort(d+1,d+n+1,cmp);
	int tim=0;
	for(int i=1;i<=n;i++)
	{
		//cout<<tim<<endl;
		//for(int j=1;j<=n;j++) cout<<pos(1,1,n,j)<<' ';
		//cout<<endl;
		int nw=pos(1,1,n,d[i].num);
		int re=d[i].num;
		if(nw==d[i].b)
		{
			stab(1,1,n,d[i].num);
			continue;
		}
		if(nw<d[i].b)
		{
			int l=re+1,r=n;
			int ans=re;
			while(l<=r)
			{
				int mid=(l+r)>>1;
				//cout<<pos(1,1,n,mid)<<' '<<d[i].b+(mid-re)<<endl;
				if(pos(1,1,n,mid)<d[i].b+(mid-re))
				{
					ans=mid;
					l=mid+1;
				}
				else r=mid-1;
			}
			//cout<<re<<' '<<ans<<endl;
			if(ans==re)
			{
				int s=d[i].b-nw;
				tim+=s;
				if(tim>d[i].t)
				{
					printf("No\n");
					return;
				}
				if(re==n)
				{
					int s=pos(1,1,n,re-1);
					update(1,1,n,re,d[i].b-s);
					stab(1,1,n,re);
					continue;
				}
				int s1=pos(1,1,n,re-1);
				int y=pos(1,1,n,re+1);
				//cout<<s1<<' '<<y<<endl;
				update(1,1,n,re+1,y-d[i].b);
				update(1,1,n,re,d[i].b-s1);
				continue;
			}
			int op=check(1,1,n,re+1,ans);
			if(op)
			{
				printf("No\n");
				return;
			}
			int g1=calc(1,1,n,re+1,ans).nxtm;
			//cout<<calc(1,1,n,3,5).r<<endl;
			//cout<<g1<<endl;
			int dy=nw;
			int s1=ans-re;
			//cout<<g1+dy*s1<<endl;
			int ut=s1*(s1+1)/2+s1*d[i].b-g1-dy*s1;
			
			ut+=d[i].b-nw;
			//cout<<ut<<endl;
			tim+=ut;
			if(tim>d[i].t)
			{
				printf("No\n");
				return;
			}
			int u;
			if(ans!=n)
			{
				u=pos(1,1,n,ans+1);
				//cout<<u<<endl;
				update(1,1,n,ans+1,u-(d[i].b+s1));
			}
			u=pos(1,1,n,re-1);
			update(1,1,n,re,d[i].b-u);
			
			reset(1,1,n,re+1,ans);
			stab(1,1,n,re);
			continue;
		}
		int l=1,r=re-1;
		int ans=re;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(pos(1,1,n,mid)>d[i].b-(re-mid))
			{
				ans=mid;
				r=mid-1;
			}
			else l=mid+1;
		}
		if(ans==re)
		{
			int s=nw-d[i].b;
			tim+=s;
			if(tim>d[i].t)
			{
				printf("No\n");
				return;
			}
			if(re==n)
			{
				int s=pos(1,1,n,re-1);
				update(1,1,n,re,d[i].b-s);
				stab(1,1,n,re);
				continue;
			}
			int s1=pos(1,1,n,re-1);
			int y=pos(1,1,n,re+1);
			update(1,1,n,re+1,y-d[i].b);
			update(1,1,n,re,d[i].b-s1);
			continue;
		}
		int op=check(1,1,n,ans,re-1);
		if(op)
		{
			printf("No\n");
			return;
		}
		int g1=calc(1,1,n,ans,re-1).nxtm;
		int dy=pos(1,1,n,ans-1);
		int s1=re-ans;
		int ut=g1+dy*s1-(d[i].b*s1-s1*(s1+1)/2);
		ut+=nw-d[i].b;
		tim+=ut;
		if(tim>d[i].t)
		{
			printf("No\n");
			return;
		}
		int u;
		if(re!=n)
		{
			u=pos(1,1,n,re+1);
			update(1,1,n,re+1,u-d[i].b);
		}
		u=pos(1,1,n,ans-1);
		update(1,1,n,ans,d[i].b-s1-u);
		
		reset(1,1,n,ans+1,re);
		stab(1,1,n,re);
		continue;
	}
	printf("Yes\n");
	
}

signed main()
{
	freopen("move.in","r",stdin);
	freopen("move.out","w",stdout);
	c=read();
	T=read();
	while(T--) work();
}

递交者: shijingyao LV 6
题目: NOISX2025D [省选联考 2025] 推箱子
语言: C++14(O2, GCC 9.3.0)
代码长度: 6.6 KiB
递交时间: 2025-3-13 11:38:18
评测时间: 2025-3-13 11:38:36

分数: 72
总耗时: ≥26073ms
峰值时间: ≥2703ms
峰值内存: ≥30.6 MiB

72 Time Exceeded

代码

信息

72 Time Exceeded

代码

信息

还没有账户？

登录