#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int maxn = 100010;
int N, Vmax, V2;
pii B[maxn];
vector<int> V[maxn];
int Xn;
vector<int> X;
unordered_map<int, int> dx;
struct BIT {
vector<int> tree, lazy;
void init() {
tree = vector<int>(4 * N, 0);
lazy = vector<int>(4 * N, 0);
}
void prop(int l, int r, int n) {
if(l != r) {
tree[2*n] += lazy[n];
lazy[2*n] += lazy[n];
tree[2*n + 1] += lazy[n];
lazy[2*n + 1] += lazy[n];
lazy[n] = 0;
}
}
void upd(int a, int b, int d, int l, int r, int n) {
if(b < l || r < a) return;
if(a <= l && r <= b) {
tree[n] += d;
lazy[n] += d;
return;
}
prop(l, r, n);
int m = (l + r)>>1;
upd(a, b, d, l, m, 2*n);
upd(a, b, d, m + 1, r, 2*n + 1);
tree[n] = max(tree[2*n], tree[2*n + 1]);
}
int quer(int a, int b, int l, int r, int n) {
if(b < l || r < a) return -1e9;
if(a <= l && r <= b) return tree[n];
prop(l, r, n);
int m = (l + r)>>1;
int L = quer(a, b, l, m, 2*n);
int R = quer(a, b, m + 1, r, 2*n + 1);
return max(L, R);
}
} bit1, bit2;
int find0(int v) {
int s = 0, e = N - 1, p = -1;
while(s <= e) {
int m = (s + e)>>1;
if(-bit2.quer(m, N - 1, 0, N - 1, 1) <= v) {
p = m;
s = m + 1;
}
else e = m - 1;
}
return p;
}
int find1(int v) {
int s = 0, e = N - 1, p = -1;
while(s <= e) {
int m = (s + e)>>1;
if(bit1.quer(m, N - 1, 0, N - 1, 1) >= v) {
p = m;
s = m + 1;
}
else e = m - 1;
}
return p;
}
int main() {
scanf("%d %d %d", &N, &Vmax, &V2);
for(int i = 0; i < N; i++) {
char t; int x; scanf("\n%c %d", &t, &x);
B[i] = { t == '+', x };
}
for(int i = 1; i < N; i++) {
X.push_back(B[i].second - B[i - 1].second);
}
sort(X.begin(), X.end());
X.resize(unique(X.begin(), X.end()) - X.begin());
Xn = X.size();
for(int i = 0; i < Xn; i++) dx[X[i]] = i;
for(int i = 1; i < N; i++) {
V[ dx[ B[i].second - B[i - 1].second ] ].push_back(i);
}
bit1.init();
bit2.init();
bit1.upd(0, N - 1, V2, 0, N - 1, 1);
bit2.upd(0, N - 1, -V2, 0, N - 1, 1);
for(int i = N - 1; i >= 1; i--) {
if(B[i].first) {
bit1.upd(0, i - 1, -1, 0, N - 1, 1);
bit2.upd(0, i - 1, 1, 0, N - 1, 1);
}
else {
bit1.upd(0, i - 1, 1, 0, N - 1, 1);
bit2.upd(0, i - 1, -1, 0, N - 1, 1);
}
}
for(int x = Xn - 1; x >= -1; x--) {
int t = find0(0);
int d = find1(Vmax);
if(t <= 0 && d <= 0) {
if(x == Xn - 1) {
printf("infinity");
return 0;
}
printf("%d %d", X[x + 1] - 1, bit1.quer(0, 0, 0, N - 1, 1));
return 0;
}
if(t < d) {
int p = find1(Vmax + 1);
if(p == -1 || p < t) {
if(x == Xn - 1) {
printf("infinity");
return 0;
}
printf("%d %d", X[x + 1] - 1, Vmax);
return 0;
}
}
else {
int p = find0(-1);
if(p == -1 || p < d) {
if(x == Xn - 1) {
printf("infinity");
return 0;
}
printf("%d %d", X[x + 1] - 1, bit1.quer(0, 0, 0, N - 1, 1));
return 0;
}
}
if(x == -1) return 0;
for(int i = 0; i < V[x].size(); i++) {
int t = B[ V[x][i] ].first;
if(t) {
bit1.upd(0, V[x][i] - 1, 1, 0, N - 1, 1);
bit2.upd(0, V[x][i] - 1, -1, 0, N - 1, 1);
}
else {
bit1.upd(0, V[x][i] - 1, -1, 0, N - 1, 1);
bit2.upd(0, V[x][i] - 1, 1, 0, N - 1, 1);
}
}
}
}
Compilation message
mp3player.cpp: In function 'int main()':
mp3player.cpp:158:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < V[x].size(); i++) {
~~^~~~~~~~~~~~~
mp3player.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &N, &Vmax, &V2);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
mp3player.cpp:86:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
char t; int x; scanf("\n%c %d", &t, &x);
~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2680 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
3064 KB |
Output is correct |
| 2 |
Correct |
7 ms |
2936 KB |
Output is correct |
| 3 |
Correct |
18 ms |
3192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
2936 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 3 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 4 |
Correct |
9 ms |
2936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
3192 KB |
Output is correct |
| 2 |
Correct |
21 ms |
3320 KB |
Output is correct |
| 3 |
Correct |
21 ms |
3324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
71 ms |
5596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
154 ms |
6072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
151 ms |
6712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
134 ms |
8800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
216 ms |
12604 KB |
Output is correct |
| 2 |
Correct |
748 ms |
16588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
361 ms |
14156 KB |
Output is correct |
| 2 |
Correct |
949 ms |
16476 KB |
Output is correct |
