#include <bits/stdc++.h>
#define int long long
#define FOR(var, bound) for (int var = 0; var < bound; var++)
#define FORB(var, lb, ub) for (int var = lb; var < ub; var++)
#define FORR(var, bound) for (int var = bound - 1; var >= 0; var--)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;
#define N 1000005
int n;
pii masts[N];
int t[N * 4];
int lazy[N * 4];
void pushdown(int n, int l, int r) {
if (lazy[n] == 0 || l == r) return;
t[n * 2] += lazy[n];
t[n * 2 + 1] += lazy[n];
lazy[n * 2] += lazy[n];
lazy[n * 2 + 1] += lazy[n];
lazy[n] = 0;
}
void update(int ql, int qr, int v, int n = 1, int tl = 0, int tr = N - 1) {
pushdown(n, tl, tr);
if (ql <= tl && tr <= qr) {
t[n] += v;
lazy[n] += v;
} else {
int m = (tl + tr) / 2;
if (ql <= m) {
update(ql, qr, v, n * 2, tl, m);
}
if (qr > m) {
update(ql, qr, v, n * 2 + 1, m + 1, tr);
}
t[n] = max(t[n * 2], t[n * 2 + 1]);
}
}
int get(int ql, int qr, int n = 1, int tl = 0, int tr = N - 1) {
pushdown(n, tl, tr);
if (ql <= tl && tr <= qr)
return t[n];
else {
int res = 0;
int m = (tl + tr) / 2;
if (ql <= m) {
res = get(ql, qr, n * 2, tl, m);
}
if (qr > m) {
res = max(res, get(ql, qr, n * 2 + 1, m + 1, tr));
}
return res;
}
}
long long getFinal(int n = 1, int tl = 0, int tr = N - 1) {
pushdown(n, tl, tr);
if (tl == tr)
return t[n] * (long long)(t[n] - 1) / 2;
else {
int m = (tl + tr) / 2;
return getFinal(n * 2, tl, m) + getFinal(n * 2 + 1, m + 1, tr);
}
}
// Returns first index such that t[i] < val
int getLastIdx(int val, int n = 1, int tl = 0, int tr = N - 1) {
if (t[n] < val) return tl;
if (tl == tr) return tr + 1;
int m = (tl + tr) / 2;
if (t[n * 2 + 1] >= val)
return getLastIdx(val, n * 2 + 1, m + 1, tr);
else
return getLastIdx(val, n * 2, tl, m);
}
void printTree(int n) {
cout << "TREE:\n";
FOR(i, n) { cout << get(i, i) << " "; }
cout << endl;
}
bool custom(pii a, pii b) {
if (a.first != b.first) {
return a.first < b.first;
}
return a.first > b.first;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef LOCAL_TEST
// freopen("sails.in", "r", stdin);
// freopen("sails.out", "w", stdout);
#endif
cin >> n;
FOR(i, n) { cin >> masts[i].first >> masts[i].second; }
sort(masts, masts + n, custom);
FOR(i, n) {
int height = masts[i].first;
int cnt = masts[i].second;
int endVal = get(height - cnt, height - cnt);
int lowestPlace = getLastIdx(endVal + 1);
int normalFill = getLastIdx(endVal);
normalFill = min(normalFill, height);
int rem = cnt;
if (normalFill < height) {
update(normalFill, height - 1, 1);
cnt -= (height - normalFill);
}
if (rem > 0) {
update(lowestPlace, lowestPlace + cnt - 1, 1);
}
#ifdef LOCAL_TEST
cout << height << " " << cnt << endl;
printTree(5);
#endif
}
cout << getFinal() << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
340 KB |
Output is correct |
2 |
Correct |
10 ms |
432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
340 KB |
Output is correct |
2 |
Correct |
10 ms |
448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
10 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
10 ms |
468 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
15 ms |
10324 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
25 ms |
33236 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
37 ms |
33536 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
53 ms |
33876 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
74 ms |
34280 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
77 ms |
34496 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
79 ms |
34680 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |