#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;
}
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);
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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
468 KB |
Output is correct |
2 |
Correct |
10 ms |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
448 KB |
Output is correct |
2 |
Correct |
11 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
468 KB |
Output is correct |
2 |
Correct |
10 ms |
464 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
10 ms |
508 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
21 ms |
28628 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
27 ms |
33340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
35 ms |
33872 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
61 ms |
34416 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
70 ms |
35204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
87 ms |
35568 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
79 ms |
35780 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |