QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#387694#3746. 千万别用树套树NYOJ-2WA 836ms12812kbC++171.4kb2024-04-12 18:54:082024-04-12 18:54:11

Judging History

This is the latest submission verdict.

  • [2024-04-12 18:54:11]
  • Judged
  • Verdict: WA
  • Time: 836ms
  • Memory: 12812kb
  • [2024-04-12 18:54:08]
  • Submitted

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct cmp{
	int l,r;
	int sum;
	int lazy;
}tr[2000005];
void push_down(int i)
{
	if(tr[i].lazy!=0)
	{
		tr[2*i].lazy+=tr[i].lazy;
		tr[i*2+1].lazy+=tr[i].lazy;
		int mid=(tr[i].l+tr[i].r)/2;
		tr[i*2].sum+=tr[i].lazy*(mid-tr[i*2].l+1);
		tr[i*2+1].sum+=tr[i].lazy*(tr[i*2+1].r-mid);
		tr[i].lazy=0;
	}
	return ;
}
void init(int i,int l,int r)
{
	tr[i].lazy=0;
	tr[i].l=l,tr[i].r=r;
	if(l==r)
	{
		tr[i].sum=0;
		return ;
	}
	int mid=(l+r)/2;
	init(i*2,l,mid);
	init(i*2+1,mid+1,r);
	tr[i].sum=tr[i*2].sum+tr[i*2+1].sum;
}
void add(int i,int l,int r)
{
	if(tr[i].r<=r&&tr[i].l>=l)
	{
		tr[i].sum+=1;
		tr[i].lazy+=1;
		return ;
	}
	push_down(i);
	if(tr[i*2].r>=l) add(i*2,l,r);
	if(tr[i*2+1].l<=r) add(i*2+1,l,r);
	tr[i].sum=tr[i*2].sum+tr[i*2+1].sum;
	return ;
}
int ask(int i,int l,int r)
{
	if(tr[i].l<=l&&tr[i].r>=r)
	{
//		cout<<tr[i].l<<" "<<tr[i].r<<endl; 
		return tr[i].sum;
	}
	if(tr[i].l>=l||tr[i].r<=r) return 0;
	int s=0;
	push_down(i);
	if(tr[i*2].r>=l) s+=ask(i*2,l,r);
	if(tr[i*2+1].l<=r) s+=ask(i*2+1,l,r);
	return s;
}
signed main()
{
//	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,m;
	while(scanf("%lld%lld",&n,&m)!=EOF)
	{
		init(1,1,n);
		while(m--)
		{
			int p;
			cin>>p;
			if(p==1)
			{
				int x,y;
				cin>>x>>y;
				add(1,x,y);
			}
			else
			{
				int x,y;
				cin>>x>>y;
				cout<<ask(1,x,y)<<"\n";
			}
		}
	}
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 836ms
memory: 12812kb

input:

100000 100000
1 48500 63742
1 43673 89780
1 6471 44388
1 68054 71541
1 30056 91431
1 49687 70537
2 46899 46900
1 5165 57954
1 85892 88481
2 18060 18062
2 45289 45289
1 18927 67848
1 17389 96139
1 63451 92197
1 15473 87341
1 15162 15744
1 76728 99645
2 48730 48731
2 20886 20888
1 9756 67424
1 23175 4...

output:

82883
137590
137590
239625
239625
430654
462709
462709
531476
581488
686034
686034
768509
768509
818515
818515
890616
894538
894538
894538
913296
913296
913296
913296
916630
1016273
1078879
1148048
1179699
1179699
1209392
1209392
1237526
1373883
1373883
1412555
1412555
1412555
1413745
1452040
145204...

result:

wrong answer 1st numbers differ - expected: '2', found: '82883'