| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 225660 | 2020-04-21T06:27:10 Z | VEGAnn | Shortcut (IOI16_shortcut) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h>
#include "shortcut.h"
#define all(x) x.begin(),x.end()
#define PB push_back
#define MP make_pair
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define ft first
#define sd second
using namespace std;
typedef long long ll;
const int N = 1000100;
const ll OO = 1e18;
pli events[N], o_events[N];
pll seg_mx[N], seg_mn[N];
ll pf[N], dst[N], c;
int n, mem_l[N], mem_r[N];
bool ok(ll mx){
bool was = 0;
ll u = -1, d = -1, l = -1, r = -1;
int ptr = 0;
for (register int it = 0; it < n; it++) {
int i = o_events[it].sd;
while (ptr < n && mx + events[ptr].ft < -pf[i] + dst[i])
ptr++;
pll cur = MP(1, 1);
if (!(seg_mx[ptr].ft == -OO || (seg_mx[ptr].ft == (pf[i] + dst[i]) && seg_mx[ptr].sd == OO))) {
cur.ft = (seg_mx[ptr].ft == (pf[i] + dst[i]) ? seg_mx[ptr].sd : seg_mx[ptr].ft);
cur.sd = (seg_mn[ptr].ft == (pf[i] - dst[i]) ? seg_mn[ptr].sd : seg_mn[ptr].ft);
if (cur.ft != -OO) {
ll cu = cur.sd + pf[i] + (mx - dst[i] - c);
ll cd = cur.ft + pf[i] - (mx - dst[i] - c);
ll cl = -cur.sd + pf[i] - (mx - dst[i] - c);
ll cr = -cur.ft + pf[i] + (mx - dst[i] - c);
if (!was){
was = 1;
u = cu; d = cd; l = cl; r = cr;
if (u < d || r < l) return 0;
} else {
u = min(u, cu);
d = max(d, cd);
if (u < d) return 0;
l = max(l, cl);
r = min(r, cr);
if (r < l) return 0;
}
}
}
}
if (!was) return 1;
l >>= 1; r >>= 1;
int l1 = 0, r1 = -1;
int r2 = -1, l2 = 0;
for (register int i = n - 1; i >= 0; i--){
while (l1 < n && pf[l1] + pf[i] < d)
l1++;
while (r1 + 1 < n && pf[r1 + 1] + pf[i] <= u)
r1++;
mem_l[i] = l1;
mem_r[i] = r1;
}
for (register int i = 0; i < n; i++) {
while (r2 < n - 1 && ((pf[i] - pf[r2 + 1]) >> 1) >= l)
r2++;
while (l2 < n && ((pf[i] - pf[l2]) >> 1) > r)
l2++;
int j1 = max(mem_l[i], l2), j2 = min(mem_r[i], r2);
if (j1 > j2) continue;
if (j1 == j2){
if (j1 != i)
return 1;
} else return 1;
}
return 0;
}
long long find_shortcut(int N, std::vector<int> l, std::vector<int> d, int C){
n = N;
c = C * 2;
ll mex = 0;
pf[0] = 0;
for (register int i = 0; i < n - 1; i++) {
pf[i + 1] = pf[i] + l[i] * 2;
dst[i] = d[i] * 2;
mex = max(mex, dst[i]);
}
dst[n - 1] = d[n - 1] * 2;
mex = max(mex, dst[n - 1]);
for (register int i = 0; i < n; i++) {
events[i] = MP(-pf[i] - dst[i], i);
o_events[i]= MP(-pf[i] + dst[i], i);
}
sort(all(events));
sort(all(o_events));
seg_mx[0] = MP(-OO, -OO);
seg_mn[0] = MP(OO, OO);
for (register int it = 1; it <= n; it++){
int j = events[it - 1].sd;
pll nw = MP(pf[j] + dst[j], pf[j] - dst[j]);
seg_mx[it] = seg_mx[it - 1];
seg_mn[it] = seg_mn[it - 1];
if (seg_mx[it].ft < nw.ft){
swap(seg_mx[it].ft, seg_mx[it].sd);
seg_mx[it].ft = nw.ft;
} else if (seg_mx[it].sd < nw.ft)
seg_mx[it].sd = nw.ft;
if (seg_mn[it].ft > nw.sd){
swap(seg_mn[it].ft, seg_mn[it].sd);
seg_mn[it].ft = nw.sd;
} else if (seg_mn[it].sd > nw.sd)
seg_mn[it].sd = nw.sd;
}
// smth smaller
ll l1 = 0, r1 = mex + pf[n - 1] / 2;
while (l1 < r1){
ll md = (l1 + r1) >> 1;
if (ok(md * 2))
r1 = md;
else l1 = md + 1;
}
return l1;
}