This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int seg[4*200005], lazy[4*200005];
void lazypropagate(int n, int l, int r) {
if (lazy[n]) {
seg[n] += lazy[n];
if (l != r) {
lazy[2*n] += lazy[n];
lazy[2*n+1] += lazy[n];
}
lazy[n] = 0;
}
}
void update(int n, int l, int r, int a, int b, int v) {
lazypropagate(n, l, r);
if (b < l || r < a) {
return;
} else if (a <= l && r <= b) {
lazy[n] += v;
lazypropagate(n, l, r);
} else {
int m = (l+r)/2;
update(2*n, l, m, a, b, v);
update(2*n+1, m+1, r, a, b, v);
seg[n] = min(seg[2*n], seg[2*n+1]);
}
}
int query(int n, int l, int r, int a, int b) {
if (b < l || r < a) {
return INT_MAX;
}
lazypropagate(n, l, r);
if (a <= l && r <= b) {
return seg[n];
} else {
int m = (l+r)/2;
return min(query(2*n, l, m, a, b), query(2*n+1, m+1, r, a, b));
}
}
int ithquery(int n, int l, int r, int i, int v) {
lazypropagate(n, l, r);
if (l == r) {
return seg[n];
} else {
int m = (l+r)/2;
if (l <= i && i <= m) {
return ithquery(2*n, l, m, i, v);
} else {
return ithquery(2*n, m+1, r, i, v);
}
}
}
int search(int n, int h) {
int l = 0, r = n;
while(l < r) {
int m = (l+r+1)/2, v;
v = query(1, 0, 100000, 0, m);
if (v > h) {
l = m;
} else {
r = m-1;
}
}
if (query(1, 0, 100000, 0, l) > h) {
return l+1;
} else {
return l;
}
}
void solve() {
int n;
cin >> n;
vector<pair<int, int>> masts(n);
for (auto &[h, k] : masts) {
cin >> h >> k;
}
sort(masts.begin(), masts.end());
for (auto [h, k] : masts) {
if (h-k == 0) {
update(1, 0, 100000, 0, h-1, 1);
continue;
}
int v1 = query(1, 0, 100000, 0, h-k), v2 = query(1, 0, 100000, 0, h-k-1);;
if (v1 != v2) {
update(1, 0, 100000, h-k, h-1, 1);
continue;
}
int ind1 = search(h-1, v1-1);
int ind2 = search(h-1, v2);
if (ind1 != h) {
update(1, 0, 100000, ind1, h-1, 1);
k -= h-ind1;
}
update(1, 0, 100000, ind2, ind2+k-1, 1);
}
int ans = 0;
for (int i = 0; i <= 100000; i++) {
int v = query(1, 0, 100000, i, i);
v--;
ans += v*(v+1)/2;
}
cout << ans << endl;
}
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
t = 1;
while(t--) {
solve();
}
}
# | 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... |