//this code makes like no difference.
//shortcutNo7.cpp is a better code.
#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> edge;
const int MAXN = 3e5 + 10;
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
template<class T>
void setmin (T &a, T b) {
if (b < a) {
a = b;
}
}
template<class T>
void setmax (T &a, T b) {
if (a < b) {
a = b;
}
}
int N;
ll C;
ll L[MAXN]; //total length
ll D[MAXN]; //distance to secondary station (i + N)
//max BIT - wow that actually sped things up!
struct fenwick {
ll bit[MAXN];
void reset() {
fill_n(bit, MAXN, LLONG_MIN);
}
void update (int x, ll v) {
for (x++; x < MAXN; x += (x & -x)) {
setmax(bit[x], v);
}
}
ll query (int x) {
//query to x EXCLUSIVE
ll res = LLONG_MIN;
for (; x; x &= (x - 1)) {
setmax(res, bit[x]);
}
return res;
}
};
fenwick fenlpd, fendml;
pair<ll, int> vlmd[MAXN], vlpd[MAXN];
ll qdml[MAXN];
bool moo (ll dia) {
//debug("DIA = %lld\n", dia);
ll xmymn = LLONG_MIN, xmymx = LLONG_MAX;
ll xpymn = LLONG_MIN, xpymx = LLONG_MAX;
//reset entire fenwick tree
fenlpd.reset();
//fendml.reset();
for (int i = 0; i <= N; i++) {
qdml[i] = LLONG_MIN;
}
//once you add dml to a range, it never changes.
/*
for (int i = 0; i < N; i++) {
debug("vlpd[%d] = (%lld, %d)\n", i, vlpd[i].fi, vlpd[i].se);
}
for (int i = 0; i < N; i++) {
debug("vlmd[%d] = (%lld, %d)\n", i, vlmd[i].fi, vlmd[i].se);
}
*/
//vlpd[vj].fi - vlmd[vi].fi > dia
int qdmlind = N;
for (int vj = 0, vi = 0; vj < N; vj++) {
int j = vlpd[vj].se;
for (; vi < N && vlpd[vj].fi - vlmd[vi].fi > dia; vi++) {
//add vi
int i = vlmd[vi].se;
fenlpd.update(i, L[i] + D[i]);
//fendml.update(i, -vlmd[vi].fi);
//debug("i = %d, j = %d. Distance = %lld\n", i, j, vlpd[vj].fi - vlmd[vi].fi);
for (; qdmlind > i; qdmlind--) {
qdml[qdmlind] = -vlmd[vi].fi;
//debug("qdml[%d] = -vlmd[%d].fi = %lld\n", qdmlind, vi, -vlmd[vi].fi);
}
}
//setmax(xmymn, (L[i] + D[i]) + (-L[j] + D[j]) - dia + C);
//setmin(xmymx, (L[i] - D[i]) + (-L[j] - D[j]) + dia - C);
//setmax(xpymn, (L[i] + D[i]) + (L[j] + D[j]) - dia + C);
//setmin(xpymx, (L[i] - D[i]) + (L[j] - D[j]) + dia - C);
ll qulpd = fenlpd.query(j);
//ll qudml = fendml.query(j);
ll qudml = qdml[j];
if (qulpd != LLONG_MIN) {
setmax(xmymn, qulpd + (-L[j] + D[j]) - dia + C);
setmin(xmymx, -qudml + (-L[j] - D[j]) + dia - C);
if (xmymn > xmymx) {
return false;
}
setmax(xpymn, qulpd + (L[j] + D[j]) - dia + C);
setmin(xpymx, -qudml + (L[j] - D[j]) + dia - C);
if (xpymn > xpymx) {
return false;
}
}
}
//debug("xmymn = %lld, xmymx = %lld. xpymn = %lld, xpymx = %lld.\n", xmymn, xmymx, xpymn, xpymx);
//basic checks
if (xmymn == LLONG_MIN) {
return true;
}
int ubxmx = 0, lbxmn = 0; //linear optimization...
int nmoveu = 0, nmovel = 0;
for (int j = 1; j < N; j++) {
ll xmn = max(xpymn - L[j], xmymn + L[j]);
ll xmx = min(xpymx - L[j], xmymx + L[j]);
if (xmn > xmx) {
continue;
}
/*
if (upper_bound(L, L + j, xmx) != lower_bound(L, L + j, xmn)) {
return true;
}
*/
while (ubxmx < j && L[ubxmx] <= xmx) {
ubxmx++;
nmoveu++;
}
while (ubxmx > 0 && L[ubxmx - 1] > xmx) {
ubxmx--;
nmoveu++;
}
while (lbxmn < j && L[lbxmn] < xmn) {
lbxmn++;
nmovel++;
}
while (lbxmn > 0 && L[lbxmn - 1] >= xmn) {
lbxmn--;
nmovel++;
}
//check that it really is O(N)...
assert(nmoveu <= 3 * N);
assert(nmovel <= 3 * N);
if (ubxmx != lbxmn) {
return true;
}
}
return false;
}
ll find_shortcut (int nnn, vector<int> lll, vector<int> ddd, int ccc) {
//very very preliminary stuff - should also init other stuff
N = nnn;
C = ccc;
L[0] = 0;
for (int i = 1; i < N; i++) {
L[i] = L[i - 1] + lll[i - 1];
}
for (int i = 0; i < N; i++) {
D[i] = ddd[i];
}
//precomp here!
for (int i = 0; i < N; i++) {
vlmd[i] = make_pair(L[i] - D[i], i);
vlpd[i] = make_pair(L[i] + D[i], i);
}
sort(vlmd, vlmd + N);
sort(vlpd, vlpd + N);
assert(!moo(70));
ll lo = 0, hi = (N + 1) * 1000000000ll;
while (hi - lo > 1) {
ll mid = (lo + hi) >> 1;
if (moo(mid)) {
hi = mid;
} else {
lo = mid;
}
}
return hi;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
2684 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
12 ms |
2788 KB |
n = 9, 110 is a correct answer |
| 3 |
Runtime error |
10 ms |
5424 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
2684 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
12 ms |
2788 KB |
n = 9, 110 is a correct answer |
| 3 |
Runtime error |
10 ms |
5424 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
2684 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
12 ms |
2788 KB |
n = 9, 110 is a correct answer |
| 3 |
Runtime error |
10 ms |
5424 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
2684 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
12 ms |
2788 KB |
n = 9, 110 is a correct answer |
| 3 |
Runtime error |
10 ms |
5424 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
2684 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
12 ms |
2788 KB |
n = 9, 110 is a correct answer |
| 3 |
Runtime error |
10 ms |
5424 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
2684 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
12 ms |
2788 KB |
n = 9, 110 is a correct answer |
| 3 |
Runtime error |
10 ms |
5424 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
2684 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
12 ms |
2788 KB |
n = 9, 110 is a correct answer |
| 3 |
Runtime error |
10 ms |
5424 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
2684 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
12 ms |
2788 KB |
n = 9, 110 is a correct answer |
| 3 |
Runtime error |
10 ms |
5424 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
