Submission #108430

#	Time	Username	Problem	Language	Result	Execution time	Memory
108430		tictaccat	Roller Coaster Railroad (IOI16_railroad)	C++14	Compilation error	0 ms	0 KiB

railroad

#include "shortcut.h"

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const ll INF = 1e18;

struct ft{
    int N; vector<ll> trLow, trHigh;
    ft(int N): N(N), trLow(N+1,INF), trHigh(N+1,-INF) {}
    pair<ll,ll> find(int i) {
        ll low = INF; ll high = -INF;
        i++;
        while (i > 0) {
            low = min(low, trLow[i]);
            high = max(high, trHigh[i]);
            i -= i&-i;
        }
        return make_pair(low,high);
    }
    void upd(int i, ll x) {
        i++;
        trLow[i] = trHigh[i] = x;
        while (i <= N) {
            trLow[i] = min(trLow[i], x);
            trHigh[i] = max(trHigh[i],x);
            i += i&-i;
        }
    }
};

int n; ll c;
vector<ll> l,d,x;
vector<ll> vals;

bool check (ll k) {

    ll difMax = INF, difMin = -INF, sumMax = INF, sumMin = -INF;

    ft sums(n), difs(n);

    for (int i = n-1; i >= 0; i--) {
        ll delta0 = k - c - d[i];
        for (int j = i+1; j < n; j++) {
            if (x[j] - x[i] + d[i] + d[j] <= k) continue;
            ll delta = delta0 - d[j];
            difMax = min(x[j] - d[j] - x[i] + delta0, difMax);
            difMin = max(x[j] + d[j] - x[i] - delta0, difMin);
            sumMax = min(x[j] - d[j] + x[i] + delta0, sumMax);
            sumMin = max(x[j] + d[j] + x[i] - delta0, sumMin);
        }

       // cout << "i: " << i << "\n";

        int queryPos = (int)(lower_bound(vals.begin(),vals.end(),k+x[i]-d[i]+1) - vals.begin());

       // cout << "qPos: " << queryPos << "\n";

        pair<ll,ll> q1 = sums.find(n-1-queryPos);
        pair<ll,ll> q2 = difs.find(n-1-queryPos);

     //   cout << k+x[i]-d[i]+1 << " " << queryPos << "\n";

       // cout << q1.first << " " << q1.second << "\n";

        difMax = min(q2.first - x[i] + delta0, difMax);
        difMin = max(q1.second - x[i] - delta0, difMin);
        sumMax = min(q2.first + x[i] + delta0, sumMax);
        sumMin = max(q1.second + x[i] - delta0, sumMin);

        int z = find(vals.begin(),vals.end(),x[i]+d[i]) - vals.begin();

        sums.upd(n-1-z, x[i] + d[i]);
        difs.upd(n-1-z, x[i] - d[i]);

    //   cout << "updPos: " << find(vals.begin(),vals.end(),x[i]+d[i]) - vals.begin() << "\n";

//       cout << "\n";

    }

    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (x[j] - x[i] < difMin) continue;
            if (x[j] - x[i] > difMax) continue;
            if (x[j] + x[i] < sumMin) continue;
            if (x[j] + x[i] > sumMax) continue;
            return true;
        }
    }
    return false;
}

long long find_shortcut(int nt, std::vector<int> lt, std::vector<int> dt, int ct) {

    n = nt; c = ct;
    l.insert(l.end(),lt.begin(), lt.end()); 
    d.insert(d.end(), dt.begin(), dt.end()); 
    x.resize(n); vals.resize(n); 

    for (int i = 1; i < n; i++) x[i] = x[i-1] + l[i-1]; //length sum from left to index i

    //values stuffs

    for (int i = 0; i < n; i++) vals[i] = x[i] + d[i];
    sort(vals.begin(),vals.end());

    //binary search

    ll k = 0;
    ll high = INF;

    for (ll b = high/2; b > 0; b /= 2) {
        while (k + b < high && !check(k+b)) {
            k += b;
          //  cout << k << "\n";
        }
    } 

    return k+1;

    return 0;
}

Compilation message (stderr)

railroad.cpp:1:10: fatal error: shortcut.h: No such file or directory
 #include "shortcut.h"
          ^~~~~~~~~~~~
compilation terminated.