#include <algorithm>
#include <iostream>
#include <vector>
#include <numeric>
#include "shortcut.h"
using namespace std;
typedef long long nagai;
vector<vector<int>> stmin, stmax;
vector<int> mpow;
void initst(int n, vector<int> val)
{
stmin.assign(20, vector<int>(n));
stmax = stmin;
mpow.resize(n);
for (int i = 2; i <= n; ++i)
mpow[i] = mpow[i >> 1] + 1;
stmin[0] = stmax[0] = val;
for (int i = 0; i < 19; ++i)
for (int j = 0; j < n; ++j)
{
stmin[i + 1][j] = min(stmin[i][j], stmin[i][min(n - 1, j + (1 << i))]);
stmax[i + 1][j] = max(stmax[i][j], stmax[i][min(n - 1, j + (1 << i))]);
}
}
nagai qmin(int i, int j)
{
int p = mpow[j - i];
return min(stmin[p][i], stmin[p][j - (1 << p)]);
}
nagai qmax(int i, int j)
{
int p = mpow[j - i];
return max(stmax[p][i], stmax[p][j - (1 << p)]);
}
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d1, int c)
{
vector<nagai> d(n);
for (int i = 0; i < n; ++i)
d[i] = d1[i];
vector<nagai> pref(n);
for (int i = 0; i < n - 1; ++i)
pref[i + 1] = pref[i] + l[i];
nagai mx = 0;
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
mx = max(mx, pref[j] - pref[i] + d[i] + d[j]);
int ib = 0, ie = n - 1;
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (mx == pref[j] - pref[i] + d[i] + d[j])
ib = max(ib, i), ie = min(ie, j);
vector<nagai> prefd(n);
for (int i = 0; i < n; ++i)
for (int j = 0; j < i; ++j)
prefd[i] = max(prefd[i], pref[i] - pref[j] + d[j]);
vector<nagai> suffd(n);
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
suffd[i] = max(suffd[i], pref[j] - pref[i] + d[j]);
auto dist = [&](int i, int j, int a, int b)
{
if (b < a)
return pref[b] - pref[i] + pref[j] - pref[a] + c;
return pref[b] - pref[a];
};
auto check = [&](int i, int j)
{
int p2 = i;
nagai curd = 0;
nagai alldst = pref[j] - pref[i] + c;
nagai diam1 = 0;
for (int k = i; k <= j; ++k)
{
while (p2 < j && curd + l[p2] <= alldst - curd - l[p2])
curd += l[p2++];
if (p2 == j && curd + c <= alldst - curd - c)
curd += c, p2 = i;
while (p2 < j && curd + l[p2] <= alldst - curd - l[p2])
curd += l[p2++];
nagai nxtl = p2 == j ? c : l[p2];
nagai nxtp2 = p2 == j ? i : p2 + 1;
for (int l = i; l <= j; ++l)
if (l < k)
diam1 = max(diam1, min(pref[j] - pref[k] + pref[l] - pref[i] + d[k] + d[l] + c, pref[k] - pref[l] + d[k] + d[l]));
else if (l > k)
diam1 = max(diam1, min(pref[j] - pref[l] + pref[k] - pref[i] + d[k] + d[l] + c, pref[l] - pref[k] + d[k] + d[l]));
// cout << k << ' ' << diam1 << endl;
// for (int l = k; l != nxtp2; l = l == j ? i : l + 1)
// diam1 = max(diam1, dist(i, j, k, l) + d[k] + d[l]);
// for (int l = nxtp2; l != k; l = l == j ? i : l + 1)
// diam1 = max(diam1, dist(i, j, l, k) + d[k] + d[l]);
// cout << k << ' ' << diam1 << ' ' << p2 << endl;
curd -= l[k];
}
nagai diam2 = 0;
for (int k = i; k <= j; ++k)
{
diam2 = max(diam2, min(pref[j] - pref[k] + suffd[j] + d[k], c + pref[k] - pref[i] + d[k] + suffd[j]));
}
return make_pair(diam1, diam2);
};
nagai ans = mx;
for (int i = 0; i < n; ++i)
{
int di1 = d[i];
d[i] = max((nagai)d[i], prefd[i]);
int L = i + 1, R = ie;
while (R - L > 1)
{
int j = (L + R) / 2;
auto p = check(i, j);
nagai diam1 = p.first;
nagai diam2 = p.second;
if (diam1 < diam2)
L = j;
else
R = j;
// cout << i << ' ' << j << ' ' << diam << ' ' << ans << endl;
}
auto p = check(i, L);
// cout << i << ' ' << L << ' ' << p.first << ' ' << p.second << endl;
ans = min(ans, max(p.first, p.second));
p = check(i, R);
// cout << R << ' ' << p.first << ' ' << p.second << endl;
ans = min(ans, max(p.first, p.second));
d[i] = di1;
}
return ans;
}
Compilation message
shortcut.cpp: In lambda function:
shortcut.cpp:86:10: warning: unused variable 'nxtl' [-Wunused-variable]
86 | nagai nxtl = p2 == j ? c : l[p2];
| ^~~~
shortcut.cpp:87:10: warning: unused variable 'nxtp2' [-Wunused-variable]
87 | nagai nxtp2 = p2 == j ? i : p2 + 1;
| ^~~~~
shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:66:7: warning: variable 'dist' set but not used [-Wunused-but-set-variable]
66 | auto dist = [&](int i, int j, int a, int b)
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 80 vs contestant 30 |
| 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 30 |
| 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 30 |
| 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 30 |
| 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 30 |
| 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 30 |
| 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 30 |
| 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 30 |
| 2 |
Halted |
0 ms |
0 KB |
- |
