#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)(4e3) + 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[n] = -INF;
mn[n] = 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);
}
}
void printPref(int N) {
FR(i, N) {
cout << query(i, i, true) << " ";
}
cout << endl;
}
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;
}
}
set<int> has;
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);
int nt1;
int nt2;
if ((now == 0 || now == Vmax) && ((has.find(n) == has.begin()) || (get(*(prev(has.find(n)))) == now))) {
return;
}
if (ad == -1) {
nt1 = findNext(n+1, true, Vmax-now+curPref, N);
nt2 = findNext(n+1, false, curPref-now-1, N);
}
else {
nt1 = findNext(n+1, true, Vmax-now+curPref+1, N);
nt2 = findNext(n+1, 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;
}
};
int main() {
// freopen("input.in", "r", stdin);
// freopen("input.out", "w", stdout);
cin.tie(0);
cin.sync_with_stdio(0);
int N, Vmax, V2;
// N = 100;
// Vmax = 100;
//// V2 = 35;
cin >> N >> Vmax >> V2;
N--;
vector<pair<int, int>> added;
char trash1;
int last = 0;
cin >> trash1 >> last;
int arr[N];
// cout << N << " " << Vmax << " " << V2 << endl;
FR(i, N) {
char c;
cin >> c;
arr[i] = (c == '+' ? 1 : -1);
// arr[i] = (rand()%2 == 0 ? 1 : -1);
add(i, N-1, arr[i]);
int cur;
cin >> cur;
// cur = last + rand()%25 + 1;
// cout << arr[i] << " " << cur << endl;
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);
has.insert(i);
}
// v0.print(N);
// vm.print(N);
// printPref(N);
last = -1;
while (added.size()) {
int store = 0;
FR(i, N) {
store += arr[i];
store = max(0, min(Vmax, store));
if (arr[i] != 0 && store != v0.get(i)) {
cout << "Diff: " << endl;
v0.print(N);
cout << i << " " << store << endl;
}
}
if (v0.get(*has.rbegin()) <= V2 && V2 <= vm.get(*has.rbegin())) {
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);
// cout << added.back().second << " " << arr[added.back().second] << endl;
add(added.back().second, N-1, -arr[added.back().second]);
rem(added.back().second);
arr[added.back().second] = 0;
has.erase(has.find(added.back().second));
// 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+1)/2;
int cur = mid;
FR(i, N) {
cur += arr[i];
cur = max(0, min(Vmax, cur));
}
if (cur <= V2) {
low = mid;
}
else {
high = mid-1;
}
}
int cur = low;
FR(i, N) {
cur += arr[i];
cur = max(0, min(Vmax, cur));
}
cout << last-1 << " " << low;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
748 KB |
Output is correct |
| 2 |
Correct |
20 ms |
748 KB |
Output is correct |
| 3 |
Correct |
261 ms |
748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
620 KB |
Output is correct |
| 2 |
Correct |
2 ms |
620 KB |
Output is correct |
| 3 |
Correct |
9 ms |
620 KB |
Output is correct |
| 4 |
Correct |
58 ms |
748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
201 ms |
876 KB |
Output is correct |
| 2 |
Correct |
416 ms |
748 KB |
Output is correct |
| 3 |
Correct |
417 ms |
748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
23728 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
23744 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1053 ms |
23920 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1094 ms |
25488 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1050 ms |
37812 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1047 ms |
37244 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
