| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 889460 |
2023-12-19T19:00:28 Z |
uped |
Sails (IOI07_sails) |
C++17 |
|
433 ms |
6484 KB |
#include <bits/stdc++.h>
using namespace std;
#define DEBUG(a) cout << #a << ": " << a << '\n';
using ll = long long;
struct lazy_segtree {
using T = ll;
using U = ll;
T value_identity = 0ll;
U operation_identity = 0ll;
U compose(U a, U b) {
return a + b;
}
T apply(T a, U b, int n) {
return a + b * n;
}
T combine(T a, T b) {
return a + b;
}
int size;
vector<T> tree;
vector<U> operations;
lazy_segtree(int n) {
size = 1;
while (size < n) size *= 2;
tree.assign(2 * size, value_identity);
operations.assign(2 * size, operation_identity);
}
void propagate(int x, int lx, int rx) {
if (rx - lx == 1) {
return;
}
int m = (lx + rx) / 2;
operations[2 * x + 1] = compose(operations[2 * x + 1], operations[x]);
operations[2 * x + 2] = compose(operations[2 * x + 2], operations[x]);
tree[2 * x + 1] = apply(tree[2 * x + 1], operations[x], m - lx);
tree[2 * x + 2] = apply(tree[2 * x + 2], operations[x], rx - m);
operations[x] = operation_identity;
}
void modify(int l, int r, int v, int x, int lx, int rx) {
propagate(x, lx, rx);
if (lx >= r || rx <= l) return;
if (l <= lx && rx <= r) {
operations[x] = compose(operations[x], v);
tree[x] = apply(tree[x], v, rx - lx);
return;
}
int m = (lx + rx) / 2;
modify(l, r, v, 2 * x + 1, lx, m);
modify(l, r, v, 2 * x + 2, m, rx);
tree[x] = combine(tree[2 * x + 1], tree[2 * x + 2]);
}
void modify(int l, int r, int v) {
modify(l, r, v, 0, 0, size);
}
T query(int l, int r, int x, int lx, int rx) {
propagate(x, lx, rx);
if (lx >= r || rx <= l) return value_identity;
if (l <= lx && rx <= r) {
return tree[x];
}
int m = (lx + rx) / 2;
T a = query(l, r, 2 * x + 1, lx, m);
T b = query(l, r, 2 * x + 2, m, rx);
return combine(a, b);
}
T query(int l, int r) {
return query(l, r, 0, 0, size);
}
T query(int i, int x, int lx, int rx) {
propagate(x, lx, rx);
if (rx - lx == 1) {
return tree[x];
}
int m = (lx + rx) / 2;
if (i < m) {
return query(i, 2 * x + 1, lx, m);
} else {
return query(i, 2 * x + 2, m, rx);
}
}
T query(int i) {
return query(i, 0, 0, size);
}
void build(vector<T>& v, int x, int lx, int rx) {
if (rx - lx == 1) {
if (lx < v.size()) {
tree[x] = v[lx];
}
return;
}
int m = (lx + rx) / 2;
build(v, 2 * x + 1, lx, m);
build(v, 2 * x + 2, m, rx);
tree[x] = combine(tree[2 * x + 1], tree[2 * x + 2]);
}
void build(vector<T>& v) {
build(v, 0, 0, size);
}
};
const int max_n = 1e5;
int lower_bnd(lazy_segtree& st, int x) {
int l = -1, r = max_n;
while (r > l + 1) {
int mid = (l + r) / 2;
if (st.query(mid) >= x) {
r = mid;
} else {
l = mid;
}
}
return r;
}
int main() {
int n;
cin >> n;
vector<pair<int, int>> v(n);
for (int i = 0; i < n; ++i) {
cin >> v[i].first >> v[i].second;
}
lazy_segtree st(max_n);
sort(v.begin(), v.end());
for (auto& [h, s] : v) {
int left = max_n - h;
int right = left + s;
//DEBUG(left);
//DEBUG(right);
if (right < max_n && st.query(right) == st.query(right - 1)) {
int right_value = st.query(right);
//DEBUG(right_value)
int after = lower_bnd(st, right_value + 1);
int first = lower_bnd(st, right_value);
//DEBUG(after);
//DEBUG(first);
int x = s - abs(left - first);
if (left > first) {
x = s;
} else {
st.modify(left, first, 1);
}
//DEBUG(x);
st.modify(after - x, after, 1);
} else {
st.modify(left, right, 1);
}
}
ll ans = 0;
for (int i = 0; i < max_n; ++i) {
long long a = st.query(i);
//if (a > 0) DEBUG(a);
ans += (a * (a - 1)) / 2;
}
cout << ans;
}
Compilation message
sails.cpp: In member function 'void lazy_segtree::build(std::vector<long long int>&, int, int, int)':
sails.cpp:102:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | if (lx < v.size()) {
| ~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
10 ms |
4444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
4560 KB |
Output is correct |
| 2 |
Correct |
10 ms |
4556 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
4560 KB |
Output is correct |
| 2 |
Correct |
10 ms |
4444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
13 ms |
4444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
15 ms |
4444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
4672 KB |
Output is correct |
| 2 |
Correct |
135 ms |
4952 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
131 ms |
4956 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
207 ms |
5472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
357 ms |
5968 KB |
Output is correct |
| 2 |
Correct |
346 ms |
6028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
402 ms |
6272 KB |
Output is correct |
| 2 |
Correct |
380 ms |
5844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
433 ms |
6484 KB |
Output is correct |
| 2 |
Correct |
421 ms |
6324 KB |
Output is correct |
