QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#387723#3746. 千万别用树套树rukongWA 837ms7668kbC++981.3kb2024-04-12 18:55:042024-04-12 18:55:05

Judging History

This is the latest submission verdict.

  • [2024-04-12 18:55:05]
  • Judged
  • Verdict: WA
  • Time: 837ms
  • Memory: 7668kb
  • [2024-04-12 18:55:04]
  • Submitted

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'