Submission #225556

#	Time	Username	Problem	Language	Result	Execution time	Memory
225556		VEGAnn	Shortcut (IOI16_shortcut)	C++14	100 / 100	1992 ms	72660 KiB

shortcut

#include <bits/stdc++.h>
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("fast-math")
#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;
vector<pli> events, o_events;
pll seg_mx, seg_mn;
ll pf[N], dst[N], c;
int n, mem_l[N], mem_r[N];
bool mrk[N];

bool ok(ll mx){
    for (int i = 0; i < n; i++)
        mrk[i] = 0;

    bool was = 0;
    ll u = -1, d = -1, l = -1, r = -1;

    int ptr = 0;
    seg_mx = MP(-OO, -OO);
    seg_mn = MP(OO, OO);

    for (int it = 0; it < n; it++) {
        int i = o_events[it].sd;

        while (ptr < n && mx + events[ptr].ft < -pf[i] + dst[i]){
            int j = events[ptr].sd;

            mrk[j] = 1;

            pll nw = MP(pf[j] + dst[j], pf[j] - dst[j]);

            if (seg_mx.ft < nw.ft){
                swap(seg_mx.ft, seg_mx.sd);
                seg_mx.ft = nw.ft;
            } else if (seg_mx.sd < nw.ft)
                seg_mx.sd = nw.ft;

            if (seg_mn.ft > nw.sd){
                swap(seg_mn.ft, seg_mn.sd);
                seg_mn.ft = nw.sd;
            } else if (seg_mn.sd > nw.sd)
                seg_mn.sd = nw.sd;

            ptr++;
        }

        pll cur = MP(1, 1);

        if (!(seg_mx.ft == -OO || (seg_mx.ft == (pf[i] + dst[i]) && seg_mx.sd == OO))) {

            cur.ft = (seg_mx.ft == (pf[i] + dst[i]) ? seg_mx.sd : seg_mx.ft);
            cur.sd = (seg_mn.ft == (pf[i] - dst[i]) ? seg_mn.sd : seg_mn.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 (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 (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 (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 (int i = 0; i < n; i++) {
        events.PB(MP(-pf[i] - dst[i], i));
        o_events.PB(MP(-pf[i] + dst[i], i));
    }

    sort(all(events));
    sort(all(o_events));

    // 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;
}

• 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