#include <vector>
#include <climits>
#include <iostream>
#include <algorithm>
#include "shortcut.h"
using namespace std;
typedef long long nagai;
nagai INF = LLONG_MAX / 4;
struct rekt
{
nagai x1, y1, x2, y2;
rekt(nagai x1, nagai y1, nagai x2, nagai y2)
: x1(x1), y1(y1), x2(x2), y2(y2)
{}
};
rekt isc(rekt a, rekt b)
{
return rekt(max(a.x1, b.x1), max(a.y1, b.y1), min(a.x2, b.x2), min(a.y2, b.y2));
}
void to_new(nagai& x, nagai& y)
{
nagai x1 = x + y;
nagai y1 = x - y;
x = x1;
y = y1;
}
void to_old(nagai& x, nagai& y)
{
nagai ox = (x + y) / 2;
nagai oy = x - ox;
x = ox;
y = oy;
}
int C = 25;
vector<vector<nagai>> sp;
vector<int> pow;
void init_sp(int n, vector<nagai> x, vector<int> d)
{
pow.resize(n + 1);
for (int i = 2; i <= n; ++i)
pow[i] = pow[i >> 1] + 1;
sp.assign(C, vector<nagai>(n));
for (int i = 0; i < n; ++i)
sp[0][i] = x[i] - d[i];
for (int i = 0; i < C - 1; ++i)
for (int j = 0; j < n; ++j)
sp[i + 1][j] = min(sp[i][j], sp[i][min(j + (1 << i), n - 1)]);
}
nagai query(int L, int R)
{
int p = pow[R - L];
return min(sp[p][L], sp[p][R - (1 << p)]);
}
bool kek(int n, vector<nagai> x, vector<int> d, int c, nagai M)
{
nagai maxjdown = -1, minjup = -1, mxdown = -INF, mnup = INF;
rekt ans = {-INF, -INF, INF, INF};
int curp = 0;
for (int i = 0; i < n; ++i)
{
while (curp < i && (x[i] - x[curp] + d[i] + d[curp] > M || query(curp, i) < x[curp] - d[curp]))
{
if (x[curp] + d[curp] < mnup)
mnup = x[curp] + d[curp], minjup = curp;
if (x[curp] - d[curp] > mxdown)
mxdown = x[curp] - d[curp], maxjdown = curp;
++curp;
}
if (maxjdown == -1)
continue;
nagai x1 = x[i];
nagai x2 = x[i];
nagai y2 = x[maxjdown] + M - c - d[i] - d[maxjdown];
nagai y1 = x[minjup] - (M - c - d[i] - d[minjup]);
if (y1 > y2)
return false;
to_new(x1, y1);
to_new(x2, y2);
swap(y1, y2);
rekt nrekt(x1, y1, x2, y2);
ans = isc(ans, nrekt);
}
curp = 0;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < i; ++j)
{
nagai x1 = x[i];
nagai y1 = x[j];
to_new(x1, y1);
if (ans.x1 <= x1 && x1 <= ans.x2 && ans.y1 <= y1 && y1 <= ans.y2)
return true;
}
}
return false;
}
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
vector<nagai> x(n);
x[0] = 0;
for (int i = 0; i < n - 1; ++i)
x[i + 1] = x[i]+ l[i];
init_sp(n, x, d);
nagai L = 0, R = INF;
while (R - L > 1)
{
nagai M = (L + R) / 2;
(kek(n, x, d, c, M) ? R : L) = M;
}
return R;
}
Compilation message
shortcut.cpp:44:13: warning: built-in function 'pow' declared as non-function [-Wbuiltin-declaration-mismatch]
44 | vector<int> pow;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 80 vs contestant 50 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 80 vs contestant 50 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 80 vs contestant 50 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 80 vs contestant 50 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 80 vs contestant 50 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 80 vs contestant 50 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 80 vs contestant 50 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 80 vs contestant 50 |
| 2 |
Halted |
0 ms |
0 KB |
- |
