Submission #99075

#	Time	Username	Problem	Language	Result	Execution time	Memory
99075		eriksuenderhauf	Shortcut (IOI16_shortcut)	C++11	100 / 100	1444 ms	36088 KiB

shortcut

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "shortcut.h"
#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;
typedef long long ll;
const ll INF = 1e17 + 7;
const int MAXN = 1e6 + 5;
ll x[MAXN], d[MAXN];
int 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;
    int l = 0, r = 0;
    bool skip = false;
    // calculate bounds
    for (int i = 0; i < n; i++) {
        while (l < r && x[i] + d[i] - (x[dif[l]] - d[dif[l]]) > len) {
            int ind = dif[l++]; // add element to set of elements producing the intersection
            if (x[ind] - d[ind] < di)
                di = x[ind] - d[ind];
            if (x[ind] + d[ind] > sm)
                sm = 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 && x[dif[r - 1]] - d[dif[r - 1]] > x[i] - d[i])
            r--;
        dif[r++] = 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