# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
890530 |
2023-12-21T12:09:10 Z |
sheldon |
Sails (IOI07_sails) |
C++14 |
|
91 ms |
6492 KB |
#include <bits/stdc++.h>
using namespace std;
struct Node {
long long sum = 0, lazy = 0;
void push (Node &left, Node &right) {
left.sum += lazy;
right.sum += lazy;
left.lazy += lazy;
right.lazy += lazy;
lazy = 0;
}
void merge (Node &left, Node &right) {
sum = left.sum + right.sum;
}
};
vector<Node> tree;
void update (int node, int l, int r, int ql, int qr, int x) {
if (ql > r || qr < l) {
return;
}
if (ql <= l && r <= qr) {
tree[node].sum += x;
tree[node].lazy += x;
return;
}
int mid = (l + r) / 2;
tree[node].push(tree[node * 2], tree[node * 2 + 1]);
update (node * 2 , l, mid, ql, qr, x);
update (node * 2 + 1, mid + 1, r, ql, qr, x);
tree[node].merge(tree[node * 2], tree[node * 2 + 1]);
}
long long query (int node, int l, int r, int ql, int qr) {
if (ql > r || qr < l) {
return 0;
}
if (ql <= l && r <= qr) {
return tree[node].sum;
}
int mid = (l + r) / 2;
tree[node].push(tree[node * 2], tree[node * 2 + 1]);
return query(node * 2, l, mid, ql, qr) + query(node * 2 + 1, mid + 1, r, ql, qr);
}
void solve() {
int n;
cin >> n;
vector<pair<int, int>> tower(n);
for (int i = 0; i < n; ++i) {
cin >> tower[i].first >> tower[i].second;
}
sort(tower.rbegin(), tower.rend());
int base = tower[0].first, idx = tower[0].first - 1;
while (__builtin_popcount(base) != 1) {
++base;
}
tree.resize(base * 2);
long long ans = 0;
for (int i = 0; i < n; ++i) {
if (idx >= tower[i].first) {
idx = tower[i].first - 1;
}
// cout << tower[i].second << ' ' << idx << ' ' << i << '\n';
if (tower[i].second - 1 <= idx) {
update (1, 0, base - 1, idx - (tower[i].second - 1), idx, 1);
idx = idx - (tower[i].second - 1) - 1;
if (idx == -1 && i != n - 1) {
idx = tower[i + 1].first - 1;
}
// edge case idx == -1
} else {
update (1, 0, base - 1, 0, idx, 1);
tower[i].second -= (idx + 1);
idx = tower[i].first - 1;
update (1, 0, base - 1, idx - (tower[i].second - 1), idx, 1);
idx = idx - (tower[i].second - 1) - 1;
}
}
for (int i = 0; i < base; ++i) {
ans += query(1, 0, base - 1, i, i) * ((query(1, 0, base - 1, i, i) - 1)) / 2;
}
cout << ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
456 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
420 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
14 ms |
1624 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
24 ms |
1884 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
44 ms |
3420 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
77 ms |
5968 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
91 ms |
6288 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
90 ms |
6492 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |