#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |