QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#631074#8286. StackswangjunruiWA 5ms10244kbC++142.8kb2024-10-11 21:51:372024-10-11 21:51:39

Judging History

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

  • [2024-10-11 21:51:39]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:10244kb
  • [2024-10-11 21:51:37]
  • 提交

answer

#include<iostream>
#include <random>
using namespace std;
struct tree
{
	int l,r,x,y,size;
	long long s,sum;
};
tree a[35000000];
int num=0;
inline int node(int x,int y)
{
	num++;
	a[num].size=1;
	a[num].x=a[num].s=x,a[num].y=y;
	a[num].sum=(long long)x*y;
	return num;
}
inline void update(int p)
{
	a[p].size=a[a[p].l].size+a[a[p].r].size+1;
	a[p].s=a[a[p].l].s+a[a[p].r].s+a[p].x;
	a[p].sum=a[a[p].l].sum+a[a[p].r].sum
	+(long long)a[p].x*a[p].y;
}
mt19937 rnd(114514);
int merge(int x,int y)
{
	if(!x||!y)
	{
		return x|y;
	}
	int p=++num;
	rnd() & 1
	?(a[p]=a[x],a[p].r=merge(a[p].r,y))
	:(a[p]=a[y],a[p].l=merge(x,a[p].l));
	update(p);
	return p;
}
int split(int p,long long k)
{
	if(!p)
	{
		return 0;
	}
	long long t=a[a[p].r].s+a[p].x;
	if(k>=t)
	{
		return split(a[p].l,k-t);
	}
	if(k<a[a[p].r].s)
	{
		int P=++num;
		a[P]=a[p];
		a[P].r=split(a[P].r,k);
		update(P);
		return P;
	}
	a[++num]=a[p],a[num].r=0;
	a[num].x-=k-a[a[p].r].s;
	update(num);
	return num;
}
long long query(int p,long long k)
{
	if(!p)
	{
		return 0;
	}
	if(k<a[a[p].l].s)
	{
		return query(a[p].l,k);
	}
	k-=a[a[p].l].s;
	if(k<=a[p].x)
	{
		return a[a[p].l].sum+k*a[p].y;
	}
	return query(a[p].r,k-a[p].x)
	+a[a[p].l].sum+(long long)a[p].x*a[p].y;
}
int n,m,A[400000];
long long d[400000];
inline void del(int p,long long v)
{
	if(a[A[p]].s<=v)
	{
		v-=a[A[p]].s;
		A[p]=0,d[p]+=v;
		return;
	}
	A[p]=split(A[p],v);
}
inline void pushdown(int p)
{
	if(d[p])
	{
		del(p<<1,d[p]);
		del((p<<1)|1,d[p]);
		d[p]=0;
	}
	if(A[p])
	{
		A[p<<1]=merge(A[p<<1],A[p]);
		A[(p<<1)|1]=merge(A[(p<<1)|1],A[p]);
		A[p]=0;
	}
}
void add(int l,int r,int ll,int rr,int x,int y,int p)
{
	if(r<ll||l>rr)
	{
		return;
	}
	if(ll<=l&&r<=rr)
	{
		A[p]=merge(A[p],node(x,y));
		return;
	}
	pushdown(p);
	int mid=l+r>>1;
	add(l,mid,ll,rr,x,y,p<<1);
	add(mid+1,r,ll,rr,x,y,(p<<1)|1);
}
void del(int l,int r,int ll,int rr,long long x,int p)
{
	if(r<ll||l>rr)
	{
		return;
	}
	if(ll<=l&&r<=rr)
	{
		del(p,x);
		return;
	}
	pushdown(p);
	int mid=l+r>>1;
	del(l,mid,ll,rr,x,p<<1);
	del(mid+1,r,ll,rr,x,(p<<1)|1);
}
long long query(int l,int r,int x,long long ll,long long rr,int p)
{
	if(l==r)
	{
		return query(A[p],rr)-query(A[p],ll-1);
	}
	pushdown(p);
	int mid=l+r>>1;
	return x<=mid?query(l,mid,x,ll,rr,p<<1)
	:query(mid+1,r,x,ll,rr,(p<<1)|1);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	while(m--)
	{
		int op;
		cin>>op;
		if(op==1)
		{
			int l,r,x,y;
			cin>>l>>r>>x>>y;
			add(1,n,l,r,x,y,1);
		}
		if(op==2)
		{
			int l,r;
			long long x;
			cin>>l>>r>>x;
			del(1,n,l,r,x,1);
		}
		if(op==3)
		{
			int x;
			long long l,r;
			cin>>x>>l>>r;
			cout<<query(1,n,x,l,r,1)<<'\n';
		}
	}
		printf("%d\n", num);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 5ms
memory: 10244kb

input:

4907 4910
2 763 3330 1
3 307 1 1
1 2262 3430 22699 89397
1 1915 4000 51541 67587
2 212 2990 9763
2 1086 2162 1
2 1813 4496 16760
1 51 2796 68005 99390
1 1267 1519 74236 66178
3 1768 23808 54314
2 900 4122 27758
3 3287 17350 28989
2 3277 4024 3633
2 444 4866 1
2 353 4219 1061
1 987 3141 99906 17320
2...

output:

0
3032090730
903396180
471569175
200648623
98486697
647114751
123945
50793012
61782451
0
0
0
762429740
321140700
871619914
536311874
5361094892
0
1792521566
6640518748
2415375780
249435711
225987900
5250788038
1145132507
140071334
0
118545795
3086405469
5646099271
84280112
1232466642
4992966775
7968...

result:

wrong answer Output contains longer sequence [length = 1623], but answer contains 1622 elements