Submission #1191248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191248		AlgorithmWarrior	Sails (IOI07_sails)	C++20	50 / 100	1096 ms	1264 KiB

sails

#include <bits/stdc++.h>

using namespace std;

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

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);
}

stack<places>sol;

void add_st(stack<places>&stv,int cnt,int ocup){
    if(!stv.empty() && stv.top().ocup==ocup)
        stv.top().cnt+=cnt;
    else
        stv.push({cnt,ocup});
}

void solve(){
    int i;
    int last_h=0;
    for(i=1;i<=n;++i){
        auto [h,k]=v[i];
        if(h>last_h)
            add_st(sol,h-last_h,0);
        stack<places>used;
        while(k){
            auto [cnt,ocup]=sol.top();
            sol.pop();
            if(cnt>k){
                add_st(used,cnt-k,ocup);
                add_st(used,k,ocup+1);
                k=0;
            }
            else{
                add_st(used,cnt,ocup+1);
                k-=cnt;
            }
        }
        while(!used.empty()){
            auto [cnt,ocup]=used.top();
            used.pop();
            add_st(sol,cnt,ocup);
        }
        last_h=h;
    }
}

long long get_ans(){
    long long sum=0;
    while(!sol.empty()){
        auto [cnt,ocup]=sol.top();
        sol.pop();
        sum+=1LL*cnt*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: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10