#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> ui(0, 1 << 30);
int rng() {
return ui(mrand);
}
const int N=100100;
int n;
struct S {
int Min,l,r;
};
S st[4*N];
int lz[4*N];
S op(S a,S b) {
if (a.Min < b.Min)
return a;
if (a.Min > b.Min)
return b;
assert(a.r+1==b.l);
return S{a.Min,a.l,b.r};
}
void push(int u) {
st[2*u].Min += lz[u],st[2*u+1].Min += lz[u];
lz[2*u]+=lz[u],lz[2*u+1]+=lz[u];
lz[u]=0;
}
void upd(int l,int r,int x,int u=1,int tl=0,int tr=N-1) {
if (l > r) return;
if (l == tl && r == tr) {
st[u].Min += x;
lz[u] += x;
return;
}
push(u);
int mid=(tl+tr)/2;
upd(l,min(mid,r),x,2*u,tl,mid);
upd(max(mid+1,l),r,x,2*u+1,mid+1,tr);
st[u]=op(st[2*u],st[2*u+1]);
}
S query(int l,int r,int u=1,int tl=0,int tr=N-1) {
if (l > r) return S{1<<30,0,0};
if (l == tl && r == tr) {
return st[u];
}
push(u);
int mid=(tl+tr)/2;
return op(query(l,min(mid,r),2*u,tl,mid),query(max(mid+1,l),r,2*u+1,mid+1,tr));
}
void build(int u=1,int tl=0,int tr=N-1) {
st[u]=S{0,tl,tr};
if (tl==tr) return;
int mid=(tl+tr)/2;
build(2*u,tl,mid);
build(2*u+1,mid+1,tr);
}
int order[N];
int h[N],k[N];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i=0;i<n;i++)
cin >> h[i] >> k[i];
iota(order,order+n,0);
sort(order,order+n,[&](int i,int j) {
return h[i] < h[j];
});
build();
for (int t=0;t<n;t++) {
int i = order[t];
vector<pair<int,int>> to_do;
// cout << i << endl;
while(k[i] > 0) {
S res = query(0,h[i] - 1);
int l = res.l;
int now = min(k[i],res.r-res.l+1);
int r = l+now-1;
to_do.emplace_back(l,r);
k[i] -= now;
upd(l,r,2*N);
// cout << l << " " << r << endl;
}
for (auto &[l,r]: to_do)
upd(l,r,-2*N+1);
}
ll ans = 0;
for (int i=0;i<N;i++) {
S Now = query(i,i);
ans += 1LL * Now.Min * (Now.Min - 1) / 2;
}
cout << ans << endl;
}
# | 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... |