QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#504729#9104. Zayin and Foresturayaha_yahaura#AC ✓222ms10924kbC++141.8kb2024-08-04 15:26:132024-08-04 15:26:14

Judging History

你现在查看的是最新测评结果

  • [2024-08-04 15:26:14]
  • 评测
  • 测评结果:AC
  • 用时:222ms
  • 内存:10924kb
  • [2024-08-04 15:26:13]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+7;
ll read(){
    ll x=0;
    char c;
    while(!isdigit(c=getchar()));
    while(isdigit(c)){
        x=x*10+(c^48);
        c=getchar();
    }
    return x;
}
ll n,m,cnt,op[N],x[N],y[N],a[N<<1],pa[N];
ll tg[N<<2];
void put(ll p,ll k){
    tg[p]+=k;
}
void modify(ll ql,ll qr,ll k,ll p=1,ll l=1,ll r=cnt){
    if(ql<=l&&r<=qr){
        put(p,k);
        return;
    }
    ll m=(l+r)>>1;
    if(ql<=m)
        modify(ql,qr,k,p<<1,l,m);
    if(qr>m)
        modify(ql,qr,k,p<<1|1,m+1,r);
}
ll query(ll x,ll p=1,ll l=1,ll r=cnt){
    if(l==r)
        return tg[p];
    ll m=(l+r)>>1;
    ll res=tg[p];
    if(x<=m)
        res+=query(x,p<<1,l,m);
    else
        res+=query(x,p<<1|1,m+1,r);
    return res;
}
void add(ll x,ll k){
    for(;x<=n;x+=x&-x){
        ll y=upper_bound(a+1,a+cnt+1,x)-a-1;
        if(!y)
            continue;
        modify(1,y,k);
    }
}
int main(){
    n=read()+1;
    m=read();
    for(ll i=1;i<=m;++i){
        op[i]=read();
        x[i]=read();
        y[i]=read()+(op[i]-1);
        if(op[i]==2){
            a[++cnt]=x[i];
            a[++cnt]=y[i];
        }
    }
    sort(a+1,a+cnt+1);
    cnt=unique(a+1,a+cnt+1)-a-1;
    for(ll i=1;i<=m;++i){
        if(op[i]==2){
            x[i]=lower_bound(a+1,a+cnt+1,x[i])-a;
            y[i]=lower_bound(a+1,a+cnt+1,y[i])-a;
        }
    }
    for(ll i=m;i;--i){
        if(op[i]==2){
            pa[x[i]]=query(x[i]);
            pa[y[i]]=query(y[i]);
        }
        else
            add(x[i],y[i]);
    }
    for(ll i=1;i<=cnt;++i)
        pa[i]=query(i)-pa[i];
    for(ll i=1;i<=m;++i){
        if(op[i]==1)
            continue;
        printf("%lld\n",pa[x[i]]-pa[y[i]]);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 19ms
memory: 8248kb

input:

1000000000 20000
2 384578735 526547442
1 64211261 592970906
1 512065247 448267721
1 44993150 127180320
1 880319036 927623947
1 170536687 572121854
1 896600029 804033011
1 666246328 754201635
1 654066651 179982083
2 240989825 984888006
2 372004567 858916479
2 76127818 98606736
1 181794163 902842353
1...

output:

0
43148875202
17613404710
0
32808578044
28190043566
15641637055
78276219892
14955165236
20262224725
105057452192
17002492367
57916137452
27165464255
72766353838
39458327919
38294102627
264448717384
0
70928519548
279674530483
88885017175
111664599432
69703816663
211506104092
104120007714
34403738515
...

result:

ok 6649 lines

Test #2:

score: 0
Accepted
time: 222ms
memory: 10036kb

input:

1000000000000000000 100000
1 384578735 526547442
1 64211261 592970906
1 512065247 448267721
1 44993150 127180320
1 880319036 927623947
1 170536687 572121854
1 896600029 804033011
2 666246328 931651408754201635
1 654066651 179982083
1 984888006 240989825
1 372004567 858916479
1 76127818 98606736
1 18...

output:

144205553442
497561506762
903930740555
878459229726
689906696633
859703313829
735231510045
1177875391120
1461659121798
1612314483744
2027462020547
1991476058156
2381861014705
2033973986301
2117738140401
2946661001323
2187638958334
2593068002437
1854182975909
2262561461341
3038788266419
3070435321746...

result:

ok 12561 lines

Test #3:

score: 0
Accepted
time: 212ms
memory: 10924kb

input:

1000000000000000000 100000
1 395661363384578735 526547442
1 843068846064211261 592970906
1 550209039512065247 448267721
1 79278526044993150 127180320
1 193676380880319036 927623947
1 81194098170536687 572121854
1 223947079896600029 804033011
2 921340893666246328 931651408754201635
1 3605022006540666...

output:

0
152171177084
261154456848
98759395571
132967101279
214003153997
109857765028
569583036989
221377921411
943235254745
1036051470108
1290577544766
795223506189
1251272020902
662604469794
907615793356
1786684858550
488655543368
1495388560030
1818589934911
151873013358
717984689394
2039336496945
378996...

result:

ok 12561 lines