#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
struct BIT {
int n;
vector<int> T;
BIT(int sz) : n(sz), T(n + 1) {}
void inc(int i, int v) {
++i;
for (; i <= n; i += i & -i) {
T[i] += v;
}
}
void incr(int l, int r) {
if (l > r) return;
inc(l, 1);
inc(r + 1, -1);
}
int val(int i) {
++i;
int res = 0;
for (; i > 0; i -= i & -i) {
res += T[i];
}
return res;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
vector<pair<int, int>> masts(n);
for (pair<int, int>& i : masts) cin >> i.first >> i.second;
sort(masts.begin(), masts.end());
BIT bit(masts.back().first);
auto last = [&bit](int k) -> int {
int lo = -1, hi = bit.n - 1;
while (lo < hi) {
int h = (lo + hi + 1) / 2;
if (bit.val(h) > k) {
hi = h - 1;
} else {
lo = h;
}
}
return lo;
};
for (pair<int, int>& i : masts) {
int st = bit.n - i.first;
int en = st + i.second - 1;
int a = max(last(bit.val(en) - 1) + 1, st);
int b = last(bit.val(en));
bit.incr(st, a - 1);
int cnt = en - a + 1;
bit.incr(b - cnt + 1, b);
}
ll ans = 0;
for (int i = 0; i < bit.n; ++i) {
ll cnt = bit.val(i);
ans += cnt * (cnt - 1) / 2;
}
cout << ans << '\n';
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... |