oj.uz

Submission #574529

# Submission time Handle Problem Language Result Execution time Memory
574529 2022-06-08T18:28:05 Z mosiashvililuka Sails (IOI07_sails) C++14
100 / 100
 262 ms 10596 KB 
#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){
    pushdown(q,w,rr);
    if(q==w){
        if(segmn[rr]>=r){
            z=q;
        }
        return;
    }
    pushdown(q,(q+w)/2,rr*2);
    pushdown((q+w)/2+1,w,rr*2+1);
    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;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 3 ms 6468 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 4 ms 6484 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 4 ms 6484 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6612 KB Output is correct
2 Correct 6 ms 8020 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 7164 KB Output is correct
2 Correct 65 ms 7328 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 7756 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 8556 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 10100 KB Output is correct
2 Correct 188 ms 10284 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 10344 KB Output is correct
2 Correct 126 ms 10036 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 10596 KB Output is correct
2 Correct 233 ms 9568 KB Output is correct