Submission #1030135

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030135		c2zi6	Shortcut (IOI16_shortcut)	C++14	100 / 100	1391 ms	90104 KiB

shortcut

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "shortcut.h"

template<typename COMPORATOR>
struct BEST {
    COMPORATOR comp;
    PLL primary;
    PLL secondary;
    BEST() {}
    BEST(ll def) {
        primary = secondary = {def, -1};
    }
    void add(ll x, ll ind) {
        if (comp(x, primary.ff)) {
            secondary = primary;
            primary = {x, ind};
        } else if (comp(x, secondary.ff)) {
            secondary = {x, ind};
        }
    }
    ll best(ll exclude) {
        if (primary.ss == exclude) return secondary.ff;
        return primary.ff;
    }
    void print() {
        cout << "primary/secondary " << primary.ff << "/" << secondary.ff << endl;
    }
};
typedef BEST<greater<ll>> MAXIMUM;
typedef BEST<less<ll>> MINIMUM;

ll solve(int n, VL l, VL d, ll C) {
    VL X(n);
    X[0] = 0;
    replr(i, 1, n-1) X[i] = X[i-1] + l[i-1];
    VI a, b;
    rep(i, n) a.pb(i), b.pb(i);
    sort(all(a), [&](int i, int j){return X[i]+d[i] > X[j]+d[j];});
    sort(all(b), [&](int i, int j){return X[i]-d[i] > X[j]-d[j];});
    auto can = [&](ll k) {
        ll mxs, mns, mxd, mnd;
        mxs = mxd = +1e18;
        mns = mnd = -1e18;
        int last = 0;
        MAXIMUM pp, mp;
        MINIMUM pm, mm;
        pp = mp = MAXIMUM(-1e18);
        pm = mm = MINIMUM(+1e18);
        for (int i : b) {
            while (last < n && X[a[last]] + d[a[last]] > X[i] - d[i] + k) {
                int j = a[last++];
                pp.add(+X[j]+d[j], j);
                pm.add(+X[j]-d[j], j);
                mp.add(-X[j]+d[j], j);
                mm.add(-X[j]-d[j], j);
            }
            setmax(mns, X[i]-k+C+d[i] + pp.best(i));
            setmin(mxs, X[i]+k-C-d[i] + pm.best(i));
            setmax(mnd, X[i]-k+C+d[i] + mp.best(i));
            setmin(mxd, X[i]+k-C-d[i] + mm.best(i));
        }
        ll verx, very, vary;
        verx = (mxs+mnd)/2;
        very = (mxs-mnd)/2;
        vary = (mns-mxd)/2;
        int l, r;
        l = lower_bound(all(X), verx) - X.begin();
        r = upper_bound(all(X), verx) - 1 - X.begin();
        for (ll y : X) if (vary <= y && y <= very) {
            ll L = max(mnd + y, mns - y);
            ll R = min(mxd + y, mxs - y);
            while (l-1 >= 0 && X[l-1] >= L) l--;
            while (l < X.size() && X[l] < L) l++;
            while (r+1 < X.size() && X[r+1] <= R) r++;
            while (r >= 0 && X[r] > R) r--;
            if (l <= r) return true;
        }
        return false;
    };
    ll L = 0, R = 1e18;
    while (L + 1 < R) {
        ll m = (L + R) / 2;
        if (can(m)) R = m;
        else L = m;
    }
    return R;
}

ll find_shortcut(int n, VI l, VI d, int c) {
    VL L, D;
    rep(i, n) L.pb(l[i]), D.pb(d[i]);
    return solve(n, L, D, c);
}

Compilation message (stderr)

shortcut.cpp: In lambda function:
shortcut.cpp:103:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |             while (l < X.size() && X[l] < L) l++;
      |                    ~~^~~~~~~~~~
shortcut.cpp:104:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             while (r+1 < X.size() && X[r+1] <= R) r++;
      |                    ~~~~^~~~~~~~~~

• 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