QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#387723 | #3746. 千万别用树套树 | rukong | WA | 837ms | 7668kb | C++98 | 1.3kb | 2024-04-12 18:55:04 | 2024-04-12 18:55:05 |
Judging History
answer
#include<iostream>
using namespace std;
const int N=100005;
int n,q,l,r,t;
struct node
{
int l,r;
int sum,add;
}tr[N*4];
void push_up(int u)
{
tr[u].sum=tr[u*2].sum+tr[u*2+1].sum;
}
void push_down(int u)
{
if(tr[u].add)
{
tr[u*2].sum=(tr[u*2].r-tr[u*2].l+1)*tr[u].add;
tr[u*2+1].sum=(tr[u*2+1].r-tr[u*2+1].l+1)*tr[u].add;
tr[u*2].add=tr[u*2+1].add=tr[u].add;
tr[u].add=0;
}
}
void build(int u,int l,int r)
{
tr[u]={l,r,0,0};
if(l==r)return ;
int mid=(l+r)/2;
build(u*2,l,mid);
build(u*2+1,mid+1,r);
}
void modify(int u,int l,int r)
{
if(tr[u].l>=l&&tr[u].r<=r)
{
tr[u].sum+=(r-l+1);
tr[u].add=1;
return ;
}
push_down(u);
int mid=(tr[u].l+tr[u].r)/2;
if(l<=mid)modify(u*2,l,r);
if(r>mid)modify(u*2+1,l,r);
push_up(u);
}
int query(int u,int l,int r)
{
if(tr[u].l>=l&&tr[u].r<=r)
{
return tr[u].sum;
}
long long ans=0;
push_down(u);
int mid=(tr[u].l+tr[u].r)/2;
if(l<=mid)ans+=query(u*2,l,mid);
if(r>mid)ans+=query(u*2+1,mid+1,r);
return ans;
}
int main()
{
while(cin>>n>>q)
{
build(1,1,n);
while(q--)
{
cin>>t>>l>>r;
if(t==1)modify(1,l,r);
else cout<<query(1,l,r)<<endl;
}
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 837ms
memory: 7668kb
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:
395610 539108 448400 647942 1544083 136205 485398 901763 630211 1585083 33780 203955 208248 2153294 965945 965945 752674 1585969 431175 1178668 519685 1435262 1435262 519685 2032900 1548311 1272968 2073197 2476150 2476150 853534 1135698 488935 1828882 687364 643148 822347 822347 643805 270997 157510...
result:
wrong answer 1st numbers differ - expected: '2', found: '395610'