#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
using namespace std;
using ll = long long;
const int MAXN = (int)(1e2) + 5;
int mx[4*MAXN];
int mn[4*MAXN];
int lzy[4*MAXN];
int INF = (int)(1e8);
void push(int n) {
lzy[2*n] += lzy[n];
lzy[2*n+1] += lzy[n];
mx[2*n] += lzy[n];
mx[2*n+1] += lzy[n];
mn[2*n] += lzy[n];
mn[2*n+1] += lzy[n];
lzy[n] = 0;
}
void pull(int n) {
mx[n] = max(mx[2*n], mx[2*n+1]);
mn[n] = min(mn[2*n], mn[2*n+1]);
}
void add(int l, int r, int v, int n = 1, int tl = 0, int tr = MAXN-1) {
if (l > tr || r < tl) {
return;
}
if (l <= tl && tr <= r) {
mx[n] += v;
mn[n] += v;
lzy[n] += v;
return;
}
push(n);
int tm = (tl + tr)/2;
add(l, r, v, 2*n, tl, tm);
add(l, r, v, 2*n+1, tm+1, tr);
pull(n);
}
void rem(int i, int n = 1, int tl = 0, int tr = MAXN-1) {
if (tl == tr) {
mx[i] = -INF;
mn[i] = INF;
return;
}
push(n);
int tm = (tl + tr)/2;
if (i <= tm) {
rem(i, 2*n, tl, tm);
}
else {
rem(i, 2*n+1, tm+1, tr);
}
pull(n);
}
int query(int l, int r, bool gmax, int n = 1, int tl = 0, int tr = MAXN-1) {
if (l > tr || r < tl) {
if (gmax) {
return INT_MIN;
}
else {
return INT_MAX;
}
}
if (l <= tl && tr <= r) {
if (gmax) {
return mx[n];
}
else {
return mn[n];
}
}
push(n);
int tm = (tl + tr)/2;
int q1 = query(l, r, gmax, 2*n, tl, tm);
int q2 = query(l, r, gmax, 2*n+1, tm+1, tr);
if (gmax) {
return max(q1, q2);
}
else {
return min(q1, q2);
}
}
int findNext(int l, bool gmax, int v, int N) {
int ini = query(l, N-1, gmax);
if (gmax) {
if (ini >= v) {
int r = N-1;
while (l < r) {
int mid = (l + r)/2;
if (query(l, mid, gmax) >= v) {
r = mid;
}
else {
l = mid+1;
}
}
return r;
}
return N;
}
else {
if (ini <= v) {
int r = N-1;
while (l < r) {
int mid = (l + r)/2;
if (query(l, mid, gmax) <= v) {
r = mid;
}
else {
l = mid+1;
}
}
return r;
}
return N;
}
}
struct Keep {
int lzy[4*MAXN];
Keep() {
memset(lzy, 0, sizeof(lzy));
}
void add(int l, int r, int v, int n = 1, int tl = 0, int tr = MAXN-1) {
if (l > tr || r < tl) {
return;
}
if (l <= tl && tr <= r) {
lzy[n] += v;
return;
}
int tm = (tl + tr)/2;
add(l, r, v, 2*n, tl, tm);
add(l, r, v, 2*n+1, tm+1, tr);
}
int get(int i, int n = 1, int tl = 0, int tr = MAXN-1, int run = 0) {
run += lzy[n];
if (tl == tr) {
return run;
}
int tm = (tl + tr)/2;
if (i <= tm) {
return get(i, 2*n, tl, tm, run);
}
return get(i, 2*n+1, tm+1, tr, run);
}
void upd(int n, int ad, int N, int Vmax) {
int now = get(n);
int curPref = query(n, n, true);
if (now == 0 || now == Vmax) {
return;
}
int nt1;
int nt2;
if (ad == 1) {
nt1 = findNext(n, true, Vmax-now+curPref, N);
nt2 = findNext(n, false, curPref-now-1, N);
}
else {
nt1 = findNext(n, true, Vmax-now+curPref+1, N);
nt2 = findNext(n, false, curPref-now, N);
}
if (nt1 > nt2) {
swap(nt1, nt2);
}
add(n, nt1-1, -ad);
}
void print(int N) {
FR(i, N) {
cout << get(i) << " ";
}
cout << endl;
}
};
void printPref(int N) {
FR(i, N) {
cout << query(i, i, true) << " ";
}
cout << endl;
}
int main() {
cin.tie(0);
cin.sync_with_stdio(0);
int N, Vmax, V2;
cin >> N >> Vmax >> V2;
N--;
vector<pair<int, int>> added;
char trash1;
int last;
cin >> trash1 >> last;
int arr[N];
FR(i, N) {
char c;
cin >> c;
arr[i] = (c == '+' ? 1 : -1);
add(i, N-1, arr[i]);
int cur;
cin >> cur;
added.push_back({cur-last, i});
last = cur;
}
sort(added.begin(), added.end());
Keep v0, vm;
int inimax = Vmax;
int inimin = 0;
FR(i, N) {
inimax += arr[i];
inimin += arr[i];
inimax = max(0, min(inimax, Vmax));
inimin = max(0, min(inimin, Vmax));
vm.add(i, i, inimax);
v0.add(i, i, inimin);
}
// v0.print(N);
// vm.print(N);
// printPref(N);
last = -1;
while (added.size()) {
if (v0.get(N-1) <= V2 && V2 <= vm.get(N-1)) {
break;
}
int cur = added.back().first;
while (added.size() && added.back().first == cur) {
vm.upd(added.back().second, arr[added.back().second], N, Vmax);
// vm.print(N);
v0.upd(added.back().second, arr[added.back().second], N, Vmax);
// v0.print(N);
add(added.back().second, N-1, -arr[added.back().second]);
rem(added.back().second);
arr[added.back().second] = 0;
// printPref(N);
added.pop_back();
}
last = cur;
}
if (last == -1) {
cout << "infinity";
}
else {
int low = 0;
int high = Vmax;
while (low < high) {
int mid = (low + high)/2;
int cur = 0;
FR(i, N) {
cur += arr[i];
cur = max(0, min(Vmax, cur));
}
if (cur >= V2) {
high = low;
}
else {
low = mid+1;
}
}
cout << last-1 << " " << high;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
1648 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
1776 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
2032 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
22 ms |
2668 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
2792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
2920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
