#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,l,r,z,zz,seg[400009],seg2[400009],segmn[400009],segmn2[400009],E,pas,za;
pair <long long, long long> p[100009];
void pushdown(long long q, long long w, long long rr){
if(q!=w){
seg2[rr*2]+=seg2[rr];
seg2[rr*2+1]+=seg2[rr];
}
seg[rr]+=seg2[rr]*(w-q+1);
segmn[rr]+=seg2[rr];
seg2[rr]=0;
}
void upd(long long q, long long w, long long rr){
pushdown(q,w,rr);
if(q>r||w<l) return;
if(q>=l&&w<=r){
seg2[rr]+=z;
pushdown(q,w,rr);
return;
}
upd(q,(q+w)/2,rr*2);
upd((q+w)/2+1,w,rr*2+1);
seg[rr]=seg[rr*2]+seg[rr*2+1];
if(segmn[rr*2+1]<=segmn[rr*2]){
segmn[rr]=segmn[rr*2+1];segmn2[rr]=segmn2[rr*2+1];
}else{
segmn[rr]=segmn[rr*2];segmn2[rr]=segmn2[rr*2];
}
}
void read(long long q, long long w, long long rr){
pushdown(q,w,rr);
if(q>r||w<l) return;
if(q>=l&&w<=r){
z+=seg[rr];
return;
}
read(q,(q+w)/2,rr*2);
read((q+w)/2+1,w,rr*2+1);
}
void READ(long long q, long long w, long long rr){
if(q==w){
if(segmn[rr]>=r){
z=q;
}
return;
}
if(segmn[rr*2]>=r){
z=(q+w)/2;
READ((q+w)/2+1,w,rr*2+1);
}else{
READ(q,(q+w)/2,rr*2);
}
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a;
for(i=1; i<=a; i++){
cin>>p[i].first>>p[i].second;
}
sort(p+1,p+a+1);
za=1;
while(za<100000) za*=2;
for(i=1; i<=za; i++){
seg[za+i-1]=-1;segmn[za+i-1]=-1;segmn2[za+i-1]=i;
}
for(i=za-1; i>=1; i--){
seg[i]=seg[i*2]+seg[i*2+1];
segmn[i]=segmn[i*2+1];segmn2[i]=segmn2[i*2+1];
}
for(i=1; i<=a; i++){
l=p[i].first-p[i].second+1;r=l;z=0;
read(1,za,1);
r=z;E=z;
z=0;
READ(1,za,1);
e=z+1;
if(e<=p[i].first){
l=e;r=p[i].first;z=0;
read(1,za,1);
pas+=z+p[i].first-e+1;
p[i].second-=p[i].first-e+1;
l=e;r=p[i].first;z=1;
upd(1,za,1);
}
r=E+1;
z=0;
READ(1,za,1);
e=z+1;
//
l=e;r=e+p[i].second-1;z=0;
read(1,za,1);
pas+=z+p[i].second;
l=e;r=e+p[i].second-1;z=1;
upd(1,za,1);
}
cout<<pas;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
6484 KB |
Output is correct |
2 |
Correct |
3 ms |
6484 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
6484 KB |
Output is correct |
2 |
Correct |
3 ms |
6456 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
6484 KB |
Output is correct |
2 |
Correct |
3 ms |
6484 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
4 ms |
6484 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
6612 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
12 ms |
7060 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
58 ms |
7436 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
89 ms |
8036 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
107 ms |
9240 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
110 ms |
9368 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
224 ms |
9584 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |