#include "shortcut.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll INF = 1e18;
struct ft{
int N; vector<ll> trLow, trHigh;
ft(int N): N(N), trLow(N+1,INF), trHigh(N+1,-INF) {}
pair<ll,ll> find(int i) {
ll low = INF; ll high = -INF;
i++;
while (i > 0) {
low = min(low, trLow[i]);
high = max(high, trHigh[i]);
i -= i&-i;
}
return make_pair(low,high);
}
void upd(int i, ll x) {
i++;
trLow[i] = trHigh[i] = x;
while (i <= N) {
trLow[i] = min(trLow[i], x);
trHigh[i] = max(trHigh[i],x);
i += i&-i;
}
}
};
int n; ll c;
vector<ll> l,d,x;
vector<ll> vals;
bool check (ll k) {
ll difMax = INF, difMin = -INF, sumMax = INF, sumMin = -INF;
ft sums(n), difs(n);
for (int i = n-1; i >= 0; i--) {
ll delta0 = k - c - d[i];
// for (int j = i+1; j < n; j++) {
// if (x[j] - x[i] + d[i] + d[j] <= k) continue;
// ll delta = delta0 - d[j];
// difMax = min(x[j] - d[j] - x[i] + delta0, difMax);
// difMin = max(x[j] + d[j] - x[i] - delta0, difMin);
// sumMax = min(x[j] - d[j] + x[i] + delta0, sumMax);
// sumMin = max(x[j] + d[j] + x[i] - delta0, sumMin);
// }
// cout << "i: " << i << "\n";
int queryPos = (int)(lower_bound(vals.begin(),vals.end(),k+x[i]-d[i]+1) - vals.begin());
// cout << "qPos: " << queryPos << "\n";
pair<ll,ll> q1 = sums.find(n-1-queryPos);
pair<ll,ll> q2 = difs.find(n-1-queryPos);
// cout << k+x[i]-d[i]+1 << " " << queryPos << "\n";
// cout << q1.first << " " << q1.second << "\n";
difMax = min(q2.first - x[i] + delta0, difMax);
difMin = max(q1.second - x[i] - delta0, difMin);
sumMax = min(q2.first + x[i] + delta0, sumMax);
sumMin = max(q1.second + x[i] - delta0, sumMin);
int z = find(vals.begin(),vals.end(),x[i]+d[i]) - vals.begin();
sums.upd(n-1-z, x[i] + d[i]);
difs.upd(n-1-z, x[i] - d[i]);
// cout << "updPos: " << find(vals.begin(),vals.end(),x[i]+d[i]) - vals.begin() << "\n";
// cout << "\n";
}
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if (x[j] - x[i] < difMin) continue;
if (x[j] - x[i] > difMax) continue;
if (x[j] + x[i] < sumMin) continue;
if (x[j] + x[i] > sumMax) continue;
return true;
}
}
return false;
}
long long find_shortcut(int nt, std::vector<int> lt, std::vector<int> dt, int ct) {
n = nt; c = ct;
l.insert(l.end(),lt.begin(), lt.end());
d.insert(d.end(), dt.begin(), dt.end());
x.resize(n); vals.resize(n);
for (int i = 1; i < n; i++) x[i] = x[i-1] + l[i-1]; //length sum from left to index i
//values stuffs
for (int i = 0; i < n; i++) vals[i] = x[i] + d[i];
sort(vals.begin(),vals.end());
vals.erase(unique(vals.begin(),vals.end()),vals.end());
//binary search
ll k = 0;
ll high = INF;
for (ll b = high/2; b > 0; b /= 2) {
while (k + b < high && !check(k+b)) {
k += b;
// cout << k << "\n";
}
}
return k+1;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
256 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 |
256 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 |
256 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
256 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
252 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 |
384 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
2 ms |
256 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
2 ms |
384 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
2 ms |
304 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 |
256 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
2 ms |
256 KB |
n = 10, 1000000343 is a correct answer |
18 |
Incorrect |
2 ms |
256 KB |
n = 10, incorrect answer: jury 3189 vs contestant 3167 |
19 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
256 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 |
256 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 |
256 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
256 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
252 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 |
384 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
2 ms |
256 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
2 ms |
384 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
2 ms |
304 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 |
256 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
2 ms |
256 KB |
n = 10, 1000000343 is a correct answer |
18 |
Incorrect |
2 ms |
256 KB |
n = 10, incorrect answer: jury 3189 vs contestant 3167 |
19 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
256 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 |
256 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 |
256 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
256 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
252 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 |
384 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
2 ms |
256 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
2 ms |
384 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
2 ms |
304 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 |
256 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
2 ms |
256 KB |
n = 10, 1000000343 is a correct answer |
18 |
Incorrect |
2 ms |
256 KB |
n = 10, incorrect answer: jury 3189 vs contestant 3167 |
19 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
256 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 |
256 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 |
256 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
256 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
252 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 |
384 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
2 ms |
256 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
2 ms |
384 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
2 ms |
304 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 |
256 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
2 ms |
256 KB |
n = 10, 1000000343 is a correct answer |
18 |
Incorrect |
2 ms |
256 KB |
n = 10, incorrect answer: jury 3189 vs contestant 3167 |
19 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
256 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 |
256 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 |
256 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
256 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
252 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 |
384 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
2 ms |
256 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
2 ms |
384 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
2 ms |
304 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 |
256 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
2 ms |
256 KB |
n = 10, 1000000343 is a correct answer |
18 |
Incorrect |
2 ms |
256 KB |
n = 10, incorrect answer: jury 3189 vs contestant 3167 |
19 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
256 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 |
256 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 |
256 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
256 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
252 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 |
384 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
2 ms |
256 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
2 ms |
384 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
2 ms |
304 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 |
256 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
2 ms |
256 KB |
n = 10, 1000000343 is a correct answer |
18 |
Incorrect |
2 ms |
256 KB |
n = 10, incorrect answer: jury 3189 vs contestant 3167 |
19 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
256 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 |
256 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 |
256 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
256 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
252 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 |
384 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
2 ms |
256 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
2 ms |
384 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
2 ms |
304 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 |
256 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
2 ms |
256 KB |
n = 10, 1000000343 is a correct answer |
18 |
Incorrect |
2 ms |
256 KB |
n = 10, incorrect answer: jury 3189 vs contestant 3167 |
19 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
256 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 |
256 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 |
256 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
256 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
252 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 |
384 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
2 ms |
256 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
2 ms |
384 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
2 ms |
304 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 |
256 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
2 ms |
256 KB |
n = 10, 1000000343 is a correct answer |
18 |
Incorrect |
2 ms |
256 KB |
n = 10, incorrect answer: jury 3189 vs contestant 3167 |
19 |
Halted |
0 ms |
0 KB |
- |