// M
#include<bits/stdc++.h>
#include "shortcut.h"
using namespace std;
typedef long long ll;
const int N = 1000006;
int n, cost, Nxt[N];
ll X[N], L[N], D[N];
inline bool Solve(ll md)
{
/*for (int i = 1; i <= n; i ++)
{
// Nxt[i] is the smallest index such that : D[i] + D[Nxt[i]] + X[Nxt[i]] - X[i] > md
// So we want the smallest index j that D[j] + X[j] > md - D[i] + X[i]
Nxt[i] = GetFirst(i + 1, md - D[i] + X[i]);
}
// I should probably build a segment tree somewhere around here ...
for (int l = 1; l <= n; l ++)
{
// Maximum possible value of i is minimum value of Nxt in [l, Nxt[l])
int i = GetMin(l, Nxt[l]);
i = min(i, GetFirst(l + 1, md - PreD[l] + X[l]));
// Now let's find the maximum possible value for r
// We should have D
}*/
ll le_sm = -1e18, ri_sm = 1e18;
ll le_mn = -1e18, ri_mn = 1e18;
for (int i = 1; i <= n; i ++)
for (int j = i + 1; j <= n; j ++)
{
// Requiring a bridge of form (a, b) where
// D[i] + D[j] + |X[i]-a| + |X[j]-b| + cost <= md
// |X[i]-a| + |X[j]-b| <= md - cost - D[i] - D[j]
ll value = md - cost - D[i] - D[j];
// Let's break it down :
// 1. X[i]-a + X[j]-b <= value ==> a + b >= X[i] + X[j] - value
// 2. X[i]-a + b-X[j] <= value ==> b - a <= value + X[j] - X[i]
// 3. a-X[i] + X[j]-b <= value ==> b - a >= X[j] - X[i] - value
// 4. a-X[i] + b-X[j] <= value ==> b + a <= value + X[i] + X[j]
le_sm = max(le_sm, X[i] + X[j] - value); // 1.
ri_sm = min(ri_sm, value + X[i] + X[j]); // 4.
le_mn = max(le_mn, X[j] - X[i] - value); // 3.
ri_mn = min(ri_mn, value + X[j] - X[i]); // 2.
}
for (int i = 1; i <= n; i ++)
for (int j = i; j <= n; j ++)
if (X[i] + X[j] >= le_sm && X[i] + X[j] <= ri_sm && X[j] - X[i] >= le_mn && X[j] - X[i] <= ri_mn)
return 1;
return 0;
}
long long find_shortcut(int _n, vector < int > _L, vector < int > _D, int _cost)
{
n = _n;
cost = _cost;
for (int i = 1; i < n; i ++)
L[i] = _L[i - 1];
for (int i = 1; i <= n; i ++)
D[i] = _D[i - 1];
for (int i = 2; i <= n; i ++)
X[i] = X[i - 1] + L[i - 1];
ll le = 0, ri = 7e15, md;
while (ri - le > 1)
{
md = (le + ri) >> 1;
if (Solve(md))
ri = md;
else
le = md;
}
return ri;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
