QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#504729 | #9104. Zayin and Forest | urayaha_yahaura# | AC ✓ | 222ms | 10924kb | C++14 | 1.8kb | 2024-08-04 15:26:13 | 2024-08-04 15:26:14 |
Judging History
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