제출 #559599

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
559599		elazarkoren	Shortcut (IOI16_shortcut)	C++17	93 / 100	2045 ms	32900 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<int, int> pii;
typedef vector<pii> vii;

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

struct SegMin {
    vi seg;
    int n;
    SegMin() {}
    SegMin(int m) {
        for (n = 1; n < m; n <<= 1);
        seg.resize(2 * n, infinity);
    }
    void update(int i, ll x) {
        for (i += n; i; i >>= 1) chkmin(seg[i], x);
    }
    ll query(int l, int r) {
        ll ans = infinity;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) chkmin(ans, seg[l++]);
            if (r & 1) chkmin(ans, seg[--r]);
        }
        return ans;
    }
};

struct SegMax {
    vi seg;
    int n;
    SegMax() {}
    SegMax(int m) {
        for (n = 1; n < m; n <<= 1);
        seg.resize(2 * n, -infinity);
    }
    void update(int i, ll x) {
        for (i += n; i; i >>= 1) chkmax(seg[i], x);
    }
    ll query(int l, int r) {
        ll ans = -infinity;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) chkmax(ans, seg[l++]);
            if (r & 1) chkmax(ans, seg[--r]);
        }
        return ans;
    }
};

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

vi vals;
inline int Val(ll y) {
    return lower_bound(all(vals), y) - vals.begin();
}
inline int Next(ll y) {
    return upper_bound(all(vals), y) - vals.begin();
}

//SegMin min_minus;
//SegMax max_plus;
int sz;

int 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;
    SegMin min_minus = SegMin(sz);
    SegMax max_plus = SegMax(sz);
    int ind = Val(d[0] - x[0]);
    min_minus.update(ind, x[0] - d[0]);
    max_plus.update(ind, x[0] + d[0]);
    for (int j = 1; j < n; j++) {
        ind = Next(k - x[j] - d[j]);
        ll min_m = min_minus.query(ind, sz);
        ll max_p = max_plus.query(ind, sz);

        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));
        ind = Val(d[j] - x[j]);
        min_minus.update(ind, x[j] - d[j]);
        max_plus.update(ind, x[j] + d[j]);
    }
    for (int i = 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);
        auto it = lower_bound(x, x + i, lower_y);
        if (it != x + i && *it <= 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];
    for (int i = 0; i < n; i++) {
        vals.push_back(d[i] - x[i]);
    }
    sort(all(vals));
    vals.erase(unique(all(vals)), vals.end());
    sz = vals.size();
//    min_minus = SegMin(sz);
//    max_plus = SegMax(sz);
//    for (int i = 0; i < n; i++) {
//        int ind = Val(d[i] - x[i]);
//        min_minus.update(ind, x[i] - d[i]);
//        max_plus.update(ind, x[i] + d[i]);
//    }
    ll begin = 0, end = 1e18, mid;
    ll max_d = 0;
    for (int i = 0; i < n; i++) {
        chkmax(begin, max_d + d[i]);
        chkmax(max_d, ll(d[i]));
    }
    while (begin < end) {
        mid = (begin + end) >> 1;
        if (Ok(mid)) {
            end = mid;
        } else begin = mid + 1;
    }
    return end;
}

ll prefix[MAX_N];

inline ll Dist(int l, int r) {
    if (l > r) swap(l, r);
    return prefix[r] - prefix[l];
}

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