/*
CEOI 2010 MP3
- Imagine we have a bitset for each potential T
- Each operation involves shifting a suffix of those bitsets left or right
- We can basically keep track of the minimum and maximum shifted values
for each bitset and check that the distance between then isn't more than
2 * Vmax
- Note that we have to constrain the min and max to be in the range
[-vmax, vmax]
- To handle this, we use a lazy segtree with range add/subtract/min/max
- For simplicity, we also coordinate compress the times between
successive button presses
- Complexity: O(N log N)
*/
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n, vmax, v2, c[200001];
struct Node {
int curr, mn, mx;
Node operator+(Node B) {
// TODO: Fix this
return {
min(vmax, max(-vmax, curr + B.curr)),
max(-vmax, min(mn, curr + B.mn)),
min(vmax, max(mx, curr + B.mx))
};
}
} segtree[800001], lazy[800001];
char op[200001];
vector<int> comp;
void push_lazy(int node, int l, int r) {
segtree[node] = segtree[node] + lazy[node];
if (l != r) {
lazy[node * 2] = lazy[node * 2] + lazy[node];
lazy[node * 2 + 1] = lazy[node * 2 + 1] + lazy[node];
}
lazy[node] = {0, 0, 0};
}
void update(int a, int b, int val, int node = 1, int l = 0, int r = comp.size() - 1) {
push_lazy(node, l, r);
if (l > b || r < a) return;
if (l >= a && r <= b) {
lazy[node] = {val, min(0, val), max(0, val)};
push_lazy(node, l, r);
} else {
int mid = (l + r) / 2;
update(a, b, val, node * 2, l, mid);
update(a, b, val, node * 2 + 1, mid + 1, r);
}
}
Node query(int pos, int node = 1, int l = 0, int r = comp.size() - 1) {
push_lazy(node, l, r);
if (l == r) return segtree[node];
int mid = (l + r) / 2;
if (pos > mid) return query(pos, node * 2 + 1, mid + 1, r);
return query(pos, node * 2, l, mid);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> vmax >> v2;
for (int i = 0; i < n; i++) {
cin >> op[i] >> c[i];
if (i) comp.push_back(c[i] - c[i - 1]);
}
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
for (int i = 1; i < n; i++) {
int pos = lower_bound(comp.begin(), comp.end(), c[i] - c[i - 1]) - comp.begin();
int val = (op[i] == '+' ? 1 : -1);
update(pos, comp.size() - 1, val);
}
for (int i = comp.size() - 1; ~i; i--) {
Node res = query(i);
int l = -res.mn - res.curr, r = vmax - res.mx + res.curr;
if (l <= v2 && v2 <= r) {
if (i == comp.size() - 1) cout << "infinity";
else {
cout << comp[i + 1] - 1 << ' ';
if (v2 == r) cout << vmax;
else cout << v2 - res.curr;
}
return 0;
}
// cout << comp[i] << ": " << res.mn << ' ' << res.mx << ' ' << res.curr << '\n';
}
cout << comp[0] - 1 << ' ' << v2;
return 0;
}
Compilation message
mp3player.cpp: In function 'int main()':
mp3player.cpp:87:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | if (i == comp.size() - 1) cout << "infinity";
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
1600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
1736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
2508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
75 ms |
2924 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
138 ms |
3276 KB |
Output is correct |
| 2 |
Incorrect |
84 ms |
5572 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
158 ms |
5576 KB |
Output is correct |
| 2 |
Incorrect |
83 ms |
5672 KB |
Output isn't correct |
