Submission #1191295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191295		AlgorithmWarrior	Sails (IOI07_sails)	C++20	100 / 100	113 ms	3384 KiB

sails

#include <bits/stdc++.h>

using namespace std;

int const INF=1e9;
int const MAX=100005;
struct bat{
    int h,k;
    bool operator<(bat ot){
        return h<ot.h;
    }
}v[MAX];
int n;

struct AINT{
    int capat[4*MAX];
    int lazy[4*MAX];
    void propagate(int nod){
        if(lazy[nod]){
            capat[2*nod]+=lazy[nod];
            lazy[2*nod]+=lazy[nod];
            capat[2*nod+1]+=lazy[nod];
            lazy[2*nod+1]+=lazy[nod];
            lazy[nod]=0;
        }
    }
    void update(int nod,int st,int dr,int a,int b,int val){
        if(a>b)
            return;
        if(a<=st && dr<=b){
            capat[nod]+=val;
            lazy[nod]+=val;
        }
        else{
            propagate(nod);
            int mij=(st+dr)/2;
            if(a<=mij)
                update(2*nod,st,mij,a,b,val);
            if(b>mij)
                update(2*nod+1,mij+1,dr,a,b,val);
            capat[nod]=capat[2*nod];
        }
    }
    int bin_search(int nod,int st,int dr,int val){
        if(st==dr)
            return dr+1;
        propagate(nod);
        int mij=(st+dr)/2;
        if(capat[2*nod+1]>val)
            return bin_search(2*nod+1,mij+1,dr,val);
        else
            return bin_search(2*nod,st,mij,val);
    }
    int get_val(int nod,int st,int dr,int pos){
        if(st==dr)
            return capat[nod];
        propagate(nod);
        int mij=(st+dr)/2;
        if(pos<=mij)
            return get_val(2*nod,st,mij,pos);
        else
            return get_val(2*nod+1,mij+1,dr,pos);
    }
}aint;

void read(){
    cin>>n;
    int i;
    for(i=1;i<=n;++i)
        cin>>v[i].h>>v[i].k;
    sort(v+1,v+n+1);
}

void solve(){
    int i;
    aint.update(1,0,MAX-5,0,0,INF);
    aint.update(1,0,MAX-5,1,MAX-5,-1);
    int last_h=0;
    for(i=1;i<=n;++i){
        auto [h,k]=v[i];
        aint.update(1,0,MAX-5,last_h+1,h,1);
        int val=aint.get_val(1,0,MAX-5,h-k+1);
        int p1=aint.bin_search(1,0,MAX-5,val);
        int p2=aint.bin_search(1,0,MAX-5,val-1);
        int len=h-p2+1;
        aint.update(1,0,MAX-5,p1,p1+k-len-1,1);
        aint.update(1,0,MAX-5,p2,h,1);
        last_h=h;
    }
}

long long get_ans(){
    long long sum=0;
    int i;
    for(i=1;i<=v[n].h;++i){
        int ocup=aint.get_val(1,0,MAX-5,i);
        sum+=1LL*ocup*(ocup-1)/2;
    }
    return sum;
}

int main()
{
    read();
    solve();
    cout<<get_ans();
    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