QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#387694 | #3746. 千万别用树套树 | NYOJ-2 | WA | 836ms | 12812kb | C++17 | 1.4kb | 2024-04-12 18:54:08 | 2024-04-12 18:54:11 |
Judging History
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'