Submission #99074

#	Time	Username	Problem	Language	Result	Execution time	Memory
99074		eriksuenderhauf	Shortcut (IOI16_shortcut)	C++11	100 / 100	1258 ms	69000 KiB

shortcut

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "shortcut.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const ll INF = 1e17 + 7;
const int MAXN = 1e6 + 5;
const double eps = 1e-9;
ll x[MAXN], d[MAXN];
pll dif[MAXN];

/*
j>i -> xi-di, xi+di are known
z+y<=len+(xj-dj)+(xi-di) -> mxsm
z+y>=(xj+dj)+(xi+di)-len -> mism
z-y<=len+(xj-dj)-(xi+di) -> mxdi
z-y>=(xj+dj)-(xi-di)-len -> midi

shortest path has to contain shortcut:
(xj+dj) - (xi-di) > k -> calc with 2 pointers
*/
bool solve(ll len, int n, ll c) {
    ll mxsm = INF, mism = -INF, mxdi = INF, midi = -INF;
    ll di = INF, sm = -INF;
    /*pll lef = {INF, -INF};
    pll rig = {-INF, -INF};*/
    int l = 0, r = 0;
    bool skip = false;
    // calculate bounds
    for (int i = 0; i < n; i++) {
        while (l < r && x[i] + d[i] - dif[l].fi > len) {
            int ind = dif[l++].se; // add element to set of elements producing the intersection
            if (x[ind] - d[ind] < di)//lef.fi - lef.se)
                di = x[ind] - d[ind];//lef = {x[ind], d[ind]};
            if (x[ind] + d[ind] > sm)//rig.fi + rig.se)
                sm = x[ind] + d[ind];//rig = {x[ind], d[ind]};
            skip = true;
        }
        if (skip) {
            mxsm = min(mxsm, di + x[i] - d[i] + len - c);
            mism = max(mism, sm + x[i] + d[i] - len + c);
            mxdi = min(mxdi, x[i] - d[i] - sm + len - c);
            midi = max(midi, x[i] + d[i] - di - len + c);
        }
        // current station dominates last used station -> remove
        // 1. cur elem (i) dominates prev (j) -> xi-di < xj-dj
        // 2. prev elem (i) dominates cur (j) -> xi+di > xj+dj
        // dominating elements have extremal sm and di -> inc di, dec sm
        while (l < r && dif[r - 1].fi > x[i] - d[i])
            r--;
        dif[r++] = {x[i] - d[i], i};
    }
    if (mxsm < mism || mxdi < midi)
        return false;
    // check if there is a shortcut satisfying this bounds
    int curdi = 0, cursm = n;
    for (int i = 0; i < n; i++) {
        while (curdi < n && x[curdi] - x[i] < midi) // violates 4.
            curdi++;
        // all indices >= curdi satisfy 4.
        while (cursm > 0 && x[cursm - 1] + x[i] >= mism) // violates 2.
            cursm--;
        // all indices >= cursm satisfy 2.
        int cur = max(max(cursm, curdi), i + 1); // shortcut with next element / all other combinations are checked
        if (cur < n && x[cur] + x[i] <= mxsm && x[cur] - x[i] <= mxdi)
            return true;
    }
    return false;
}

ll find_shortcut(int n, vi l, vi d2, int c) {
    for (int i = 0; i < n; i++) {
        d[i] = d2[i];
        if (i == 0)
            x[i] = 0;
        else
            x[i] = x[i - 1] + l[i - 1];
    }
    ll lo = 0, hi = INF, ret = -1;
    while (lo <= hi) {
        ll mi = (lo + hi) / 2;
        if (solve(mi, n, c))
            hi = mi - 1, ret = mi;
        else
            lo = mi + 1;
    }
    return ret;
}

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 33 / 33
• Subtask 6: 22 / 22
• Subtask 7: 4 / 4
• Subtask 8: 3 / 3