Submission #1191248

#TimeUsernameProblemLanguageResultExecution timeMemory
1191248AlgorithmWarriorSails (IOI07_sails)C++20
50 / 100
1096 ms1264 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...