Submission #559633

#	Time	Username	Problem	Language	Result	Execution time	Memory
559633		elazarkoren	Shortcut (IOI16_shortcut)	C++17	97 / 100	2045 ms	39684 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
//#define int ll
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;

const int MAX_N = 1e6 + 5;
const ll infinity = 1e18;

ll x[MAX_N];
ll d[MAX_N];
ll c;

int n;

int ind1[MAX_N];
int ind2[MAX_N];

//(i < j)
//xj - xi + di + dj > k  -->
//di - xi > k - xj - dj

//di + dj + |xi - y| + |xj - z| + c <= k -->
//  (xi - di) + (xj - dj) + (k - c) >= y + z
//  (xi + di) + (xj + dj) - (k - c) <= y + z
//  (xi - di) - (xj + dj) + (k - c) >= y - z
//  (xi + di) - (xj - dj) - (k - c) <= y - z

bool Ok(ll k) {
    ll lower_plus = -infinity, lower_minus = -infinity;
    ll upper_plus = infinity, upper_minus = infinity;
    pii p1 = {-infinity, -infinity}, p2 = {infinity, infinity};
    bitset<MAX_N> visited;
    for (int j1 = 0, i = 0; j1 < n; j1++) {
        int j = ind1[j1];
        while (i < n && x[j] + d[j] - (x[ind2[i]] - d[ind2[i]]) > k) {
            ll v = x[ind2[i]] + d[ind2[i]];
            if (v >= p1.x) {
                p1.y = p1.x;
                p1.x = v;
            } else if (v > p1.y) p1.y = v;
            v = x[ind2[i]] - d[ind2[i]];
            if (v <= p2.x) {
                p2.y = p2.x;
                p2.x = v;
            } else if (v < p2.y) p2.y = v;
            visited[ind2[i]] = true;
            i++;
        }

        ll max_p = p1.x, min_m = p2.x;
        if (visited[j] && max_p == x[j] + d[j]) max_p = p1.y;
        if (visited[j] && min_m == x[j] - d[j]) min_m = p2.y;
        chkmax(lower_plus, max_p + x[j] + d[j] - (k - c));
        chkmax(lower_minus, max_p - (x[j] - d[j]) - (k - c));
        chkmin(upper_plus, min_m + (x[j] - d[j]) + (k - c));
        chkmin(upper_minus, min_m - (x[j] + d[j]) + (k - c));
    }
    for (int i = 1, j = 0; i < n; i++) {
        ll z = x[i];
        ll lower_y = max(lower_minus + z, lower_plus - z);
        ll upper_y = min(upper_minus + z, upper_plus - z);
        while (j < i && x[j] < lower_y) j++;
        while (j && x[j - 1] >= lower_y) j--;
        if (j != i && x[j] <= upper_y) return true;
    }
    return false;
}

ll find_shortcut(int32_t N, vector<int32_t> l, vector<int32_t> D, int32_t C) {
    n = N;
    c = C;
    for (int i = 1; i < n; i++) x[i] = x[i - 1] + l[i - 1];
    for (int i = 0; i < n; i++) d[i] = D[i], ind1[i] = ind2[i] = i;
    sort(ind1, ind1 + n, [&] (int i, int j) {
        return x[i] + d[i] < x[j] + d[j];
    });
    sort(ind2, ind2 + n, [&] (int i, int j) {
        return x[i] - d[i] < x[j] - d[j];
    });
    ll begin = 0, end = d[0], mid;
    ll max_d = 0;
    for (int i = 0; i < n; i++) {
        chkmax(begin, max_d + d[i]);
        chkmax(max_d, ll(d[i]));
    }
    int j = 0;
    for (int i = 1; i < n; i++) {
        chkmax(end, d[j] + d[i] + x[i] - x[j]);
        if (d[i] > x[i] - x[j] + d[j]) j = i;
    }
    while (begin < end) {
        mid = (begin + end) >> 1;
        if (Ok(mid)) {
            end = mid;
        } else begin = mid + 1;
    }
    return end;
}

• 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: 0 / 3