QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#387695 | #3746. 千万别用树套树 | NYOJ-3 | WA | 750ms | 11892kb | C++17 | 1.4kb | 2024-04-12 18:54:08 | 2024-04-12 18:54:11 |
Judging History
answer
#include<iostream>
#include<algorithm>
#include<math.h>
#include<map>
#include<string.h>
#include<queue>
#define int long long
#define endl "\n";
using namespace std;
struct cmp{
int l,r,sum;
int lazy;
}tr[2000005];
void push_down(int i)
{
if(tr[i].lazy)
{
tr[i*2].sum+=tr[i].lazy;
tr[i*2+1].sum+=tr[i].lazy;
tr[i*2].lazy+=tr[i].lazy;
tr[i*2+1].lazy+=tr[i].lazy;
tr[i].lazy=0;
}
}
void init(int i,int l,int r)
{
// cout<<l<<" "<<r<<endl;
tr[i].sum=0;
tr[i].l=l;
tr[i].r=r;
tr[i].lazy=0;
if(l==r) return ;
int mid=(l+r)/2;
init(i*2,l,mid);
init(i*2+1,mid+1,r);
}
void add(int l,int r,int i)
{
if(l<=tr[i].l&&tr[i].r<=r)
{
tr[i].sum+=1;
tr[i].lazy+=1;
return ;
}
push_down(i);
if(tr[i*2].r>=l) add(l,r,i*2);
if(tr[i*2+1].l<=r) add(l,r,i*2+1);
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,q;
while(scanf("%lld%lld",&n,&q)!=EOF)
{
init(1,1,n);
while(q--)
{
int a,x,y;
cin>>a>>x>>y;
if(x>y) swap(x,y);
if(a==1)
{
add(x,y,1);
}
else
{
cout<<ask(1,x,y)<<endl;
}
}
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 750ms
memory: 11892kb
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:
186 306 306 741 741 1002 1270 1270 1581 1874 2509 2509 3284 3284 3548 3548 4176 4473 4473 4473 4856 4856 4856 4856 4986 5541 5996 6768 7002 7002 7311 7311 7686 8567 8567 9070 9070 9070 9373 9781 9781 9781 10334 10774 10774 10774 10774 10774 11003 11003 11003 11003 12341 13235 13235 13235 13235 13235...
result:
wrong answer 1st numbers differ - expected: '2', found: '186'