#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 1e5+5, INF = 4e18+9;
int n;
struct mast{
int h, k;
};
mast a[maxn];
bool cmp(mast a, mast b){
return a.h < b.h;
}
void inp(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i].h >> a[i].k;
}
}
int N, T[4*maxn], lz[4*maxn], Tmx[4*maxn];
void build_segtree(){
N = 1;
while(N < 1e5){
N*=2;
}
}
void down(int node, int low, int high){
int len = high-low+1;
for(int child = node*2; child <= node*2+1; child++){
if(child >= 2*N) continue;
lz[child] += lz[node];
}
T[node]+=lz[node]*len;
Tmx[node]+=lz[node];
lz[node] = 0;
}
void upd(int node, int low, int high, int l, int r, ll x){
if(r < l) return;
down(node, low, high);
if(low > r || l > high){
return;
}
if(low >= l && r >= high){
lz[node] += x;
down(node, low, high);
return;
}
int mid = (low+high)/2;
upd(node*2, low, mid, l, r, x);
upd(node*2+1, mid+1, high, l, r, x);
T[node] = T[node*2]+T[node*2+1];
Tmx[node] = max(Tmx[node*2], Tmx[node*2+1]);
}
int get_sum(int node, int low, int high, int l, int r){
if(r < l) r = l;
down(node, low, high);
if(low > r || l > high){
return 0;
}
if(low >= l && r >= high){
return T[node];
}
int mid = (low+high)/2;
return get_sum(node*2, low, mid, l, r)+get_sum(node*2+1, mid+1, high, l, r);
}
int get_max(int node, int low, int high, int l, int r){
if(r < l) r = l;
down(node, low, high);
if(low > r || l > high){
return 0;
}
if(low >= l && r >= high){
return Tmx[node];
}
int mid = (low+high)/2;
return max(get_max(node*2, low, mid, l, r), get_max(node*2+1, mid+1, high, l, r));
}
int get_pos(int node, int low, int high, ll k){
if(low == high){
if(Tmx[node] < k){
return 0;
}
return low;
}
int mid = (low+high)/2;
down(node, low, high);
down(node*2, low, mid);
down(node*2+1, mid+1, high);
if(Tmx[node*2+1] >= k){
return get_pos(node*2+1, mid+1, high, k);
}else{
return get_pos(node*2, low, mid, k);
}
}
void solve(){
sort(a+1, a+1+n, cmp);
build_segtree();
int M, k;
for(int i = 1; i <= n; i++){
M = a[i].h; k = a[i].k;
ll x = get_sum(1, 1, N, M-k+1, M-k+1);
int u = get_pos(1, 1, N, x);
int d = get_pos(1, 1, N, x+1)+1;
u = min(u, M);
d = min(d, M);
upd(1, 1, N, u+1, M, 1);
upd(1, 1, N, d, d+u-(M-k+1), 1);
}
ll ans = 0;
for(int i = 1; i <= M; i++){
ll x = get_sum(1, 1, N, i, i);
ans += x*(x-1)/2;
}
cout << ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
inp();
solve();
}
Compilation message
wall.cpp: In function 'void solve()':
wall.cpp:111:22: warning: 'M' may be used uninitialized in this function [-Wmaybe-uninitialized]
111 | for(int i = 1; i <= M; i++){
| ~~^~~~
/usr/bin/ld: /tmp/ccd7lwfZ.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccunicxZ.o:wall.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccd7lwfZ.o: in function `main':
grader.cpp:(.text.startup+0x133): undefined reference to `buildWall(int, int, int*, int*, int*, int*, int*)'
collect2: error: ld returned 1 exit status
