Submission #574530

#	Time	Username	Problem	Language	Result	Execution time	Memory
574530		mosiashvililuka	Sails (IOI07_sails)	C++14	100 / 100	260 ms	7516 KiB

sails

#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],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];
    }else{
        segmn[rr]=segmn[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;
    }
    for(i=za-1; i>=1; i--){
        seg[i]=seg[i*2]+seg[i*2+1];
        segmn[i]=segmn[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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10