#include "shortcut.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector <int> dif_ord, sum_ord;
vector <ll> x, d;
inline bool check(ll k, int n, int c) {
vector <int> sgn = {1, -1};
int pos[2][2][2][2];
ll vals[2][2][2][2];
memset(pos, 0, sizeof(pos));
for(int conf = 0; conf < 8; conf++) {
vals[conf >> 2][(conf >> 1) & 1][0][conf & 1] = -1e18;
vals[conf >> 2][(conf >> 1) & 1][1][conf & 1] = 1e18;
}
auto upd = [&](int p, int conf) {
int a = (conf >> 2), b = (conf >> 1) % 2, c = conf % 2;
int v = x[p] * sgn[a] + d[p] * sgn[b];
if(c == 0) { // mx
if(vals[a][b][c][0] < v) {
pos[a][b][c][1] = pos[a][b][c][0];
vals[a][b][c][1] = vals[a][b][c][0];
pos[a][b][c][0] = p;
vals[a][b][c][0] = v;
}
else if(vals[a][b][c][1] < v) {
pos[a][b][c][1] = p;
vals[a][b][c][1] = v;
}
}
else { // mn
if(vals[a][b][c][0] > v) {
pos[a][b][c][1] = pos[a][b][c][0];
vals[a][b][c][1] = vals[a][b][c][0];
pos[a][b][c][0] = p;
vals[a][b][c][0] = v;
}
else if(vals[a][b][c][1] > v) {
pos[a][b][c][1] = p;
vals[a][b][c][1] = v;
}
}
};
int i = 0;
ll A = -1e18, B = 1e18, a = -1e18, b = 1e18;
auto get = [&](int a, int b, int c, int p) {
if(pos[a][b][c][0] == p) {
return vals[a][b][c][1];
}
return vals[a][b][c][0];
};
for(auto j : sum_ord) {
while(i < n && x[dif_ord[i]] - d[dif_ord[i]] < x[j] + d[j] - k) {
for(int conf = 0; conf < 8; conf++) {
upd(dif_ord[i], conf);
}
i++;
}
B = min(B, (k - c) + x[j] - d[j] + get(0, 1, 1, j));
A = max(A, x[j] + d[j] - (k - c) + get(0, 0, 0, j));
b = min(b, (k - c) + x[j] - d[j] - get(0, 0, 0, j));
a = max(a, x[j] + d[j] - (k - c) - get(0, 1, 1, j));
}
//cerr << k << " " << a << " " << b << " " << A << " " << B << "\n";
// A <= y + z <= B
// a <= z - y <= b
if(A > B || a > b) {
return 0;
}
int pa = 1, pb = 1;
int pc = n, pd = n;
for(i = 1; i <= n; i++) {
while(pd > 0 && x[i] + x[pd] > B) {
pd--;
}
pc = min(pc, n);
while(pc > 0 && x[i] + x[pc] >= A) {
pc--;
}
pc++;
pa = max(pa, 1);
while(pa <= n && x[i] - x[pa] >= a) {
pa++;
}
pa--;
while(pb <= n && x[i] - x[pb] > b) {
pb++;
}
if(max(pc, pb) <= min(pa, pd) && max(pc, pb) <= i) {
return 1;
}
}
return 0;
}
long long find_shortcut(int n, vector<int> l, vector<int> D, int c) {
x.resize(n + 1), d.resize(n + 1);
int i;
for(i = 2; i <= n; i++) {
x[i] = x[i - 1] + l[i - 2];
}
for(i = n; i >= 1; i--) {
d[i] = D[i - 1];
}
dif_ord.resize(n), sum_ord.resize(n);
iota(dif_ord.begin(), dif_ord.end(), 1);
iota(sum_ord.begin(), sum_ord.end(), 1);
sort(dif_ord.begin(), dif_ord.end(), [&](const int &a, const int &b) {
return x[a] - d[a] < x[b] - d[b];
});
sort(sum_ord.begin(), sum_ord.end(), [&](const int &a, const int &b) {
return x[a] + d[a] < x[b] + d[b];
});
ll res = 0;
for(ll step = 1LL << 50; step; step >>= 1) {
if(check(res + step, n, c) == 0) {
res += step;
}
}
//check(80, n, c);
return res + 1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
376 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
256 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
376 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
256 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
2 ms |
376 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
376 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
376 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
2 ms |
256 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
2 ms |
256 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
2 ms |
376 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
2 ms |
376 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
2 ms |
256 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
2 ms |
376 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
2 ms |
256 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
2 ms |
376 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
2 ms |
376 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
2 ms |
376 KB |
n = 10, 3189 is a correct answer |
19 |
Incorrect |
2 ms |
376 KB |
n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
376 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
256 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
376 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
256 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
2 ms |
376 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
376 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
376 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
2 ms |
256 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
2 ms |
256 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
2 ms |
376 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
2 ms |
376 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
2 ms |
256 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
2 ms |
376 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
2 ms |
256 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
2 ms |
376 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
2 ms |
376 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
2 ms |
376 KB |
n = 10, 3189 is a correct answer |
19 |
Incorrect |
2 ms |
376 KB |
n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
376 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
256 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
376 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
256 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
2 ms |
376 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
376 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
376 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
2 ms |
256 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
2 ms |
256 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
2 ms |
376 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
2 ms |
376 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
2 ms |
256 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
2 ms |
376 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
2 ms |
256 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
2 ms |
376 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
2 ms |
376 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
2 ms |
376 KB |
n = 10, 3189 is a correct answer |
19 |
Incorrect |
2 ms |
376 KB |
n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
376 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
256 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
376 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
256 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
2 ms |
376 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
376 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
376 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
2 ms |
256 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
2 ms |
256 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
2 ms |
376 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
2 ms |
376 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
2 ms |
256 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
2 ms |
376 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
2 ms |
256 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
2 ms |
376 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
2 ms |
376 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
2 ms |
376 KB |
n = 10, 3189 is a correct answer |
19 |
Incorrect |
2 ms |
376 KB |
n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
376 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
256 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
376 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
256 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
2 ms |
376 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
376 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
376 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
2 ms |
256 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
2 ms |
256 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
2 ms |
376 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
2 ms |
376 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
2 ms |
256 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
2 ms |
376 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
2 ms |
256 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
2 ms |
376 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
2 ms |
376 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
2 ms |
376 KB |
n = 10, 3189 is a correct answer |
19 |
Incorrect |
2 ms |
376 KB |
n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
376 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
256 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
376 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
256 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
2 ms |
376 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
376 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
376 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
2 ms |
256 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
2 ms |
256 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
2 ms |
376 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
2 ms |
376 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
2 ms |
256 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
2 ms |
376 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
2 ms |
256 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
2 ms |
376 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
2 ms |
376 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
2 ms |
376 KB |
n = 10, 3189 is a correct answer |
19 |
Incorrect |
2 ms |
376 KB |
n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
376 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
256 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
376 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
256 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
2 ms |
376 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
376 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
376 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
2 ms |
256 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
2 ms |
256 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
2 ms |
376 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
2 ms |
376 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
2 ms |
256 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
2 ms |
376 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
2 ms |
256 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
2 ms |
376 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
2 ms |
376 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
2 ms |
376 KB |
n = 10, 3189 is a correct answer |
19 |
Incorrect |
2 ms |
376 KB |
n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
376 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
256 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
376 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
256 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
2 ms |
376 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
376 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
376 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
2 ms |
256 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
2 ms |
256 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
2 ms |
376 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
2 ms |
376 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
2 ms |
256 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
2 ms |
376 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
2 ms |
256 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
2 ms |
376 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
2 ms |
376 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
2 ms |
376 KB |
n = 10, 3189 is a correct answer |
19 |
Incorrect |
2 ms |
376 KB |
n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000 |
20 |
Halted |
0 ms |
0 KB |
- |