Submission #641195

#	Time	Username	Problem	Language	Result	Execution time	Memory
641195		piOOE	Shortcut (IOI16_shortcut)	C++17	100 / 100	1486 ms	111960 KiB

shortcut

#include <bits/stdc++.h>
#include "shortcut.h"

using namespace std;
using ll = long long;

constexpr int N = 1000001;
constexpr ll inf = 0x3f3f3f3f3f3f3f3f;

ll x[N];
ll pref_sum[N], pref_diff[N]; //max x[i] + d[i], min x[i] - d[i] on prefix in sorted by diff order
ll sum[N], diff[N], sum_s[N], diff_s[N], sum_d[N], diff_d[N]; //x[ord_s[i]] + d[ord_s[i]], etc.

int ord[N];

ll find_shortcut(int n, vector<int> l, vector<int> d, int c) {
    for (int i = 0; i < n - 1; ++i) {
        x[i + 1] = x[i] + l[i];
    }

    iota(ord, ord + n, 0);

    for (int i = 0; i < n; ++i) {
        sum[i] = x[i] + d[i];
        diff[i] = x[i] - d[i];
    }

    sort(ord, ord + n, [](int i, int j) {
        return diff[i] < diff[j];
    });
    for (int i = 0; i < n; ++i) {
        sum_d[i] = sum[ord[i]];
        diff_d[i] = diff[ord[i]];
    }

    pref_sum[0] = -inf, pref_diff[0] = inf;
    for (int i = 0; i < n; ++i) {
        pref_sum[i + 1] = max(pref_sum[i], sum_d[i]);
        pref_diff[i + 1] = min(pref_diff[i], diff_d[i]);
    }

    sort(ord, ord + n, [](int i, int j) {
        return sum[i] < sum[j];
    });
    for (int i = 0; i < n; ++i) {
        sum_s[i] = sum[ord[i]];
        diff_s[i] = diff[ord[i]];
    }


    auto check = [&](ll k) -> bool {
        ll min_sum = -inf, max_sum = inf, min_diff = -inf, max_diff = inf;

        for (int i = 0, j = 0; j < n; ++j) {
            while (i < n && sum_s[j] - diff_d[i] > k) {
                ++i;
            }

            if (sum_s[j] - diff_s[j] > k) {
                //this is to prevent j being matched with itself
                int x = ord[j];
                for (int y = 0; y < x; ++y) {
                    if (sum[x] - diff[y] > k) {
                        k -= c;
                        min_sum = max(min_sum, sum[x] + sum[y] - k);
                        max_sum = min(max_sum, k + diff[x] + diff[y]);
                        min_diff = max(min_diff, sum[x] - diff[y] - k);
                        max_diff = min(max_diff, k + diff[x] - sum[y]);
                        k += c;
                    }
                }
            } else if (i > 0) {
                k -= c;
                min_sum = max(min_sum, sum_s[j] + pref_sum[i] - k);
                max_sum = min(max_sum, k + diff_s[j] + pref_diff[i]);
                min_diff = max(min_diff, sum_s[j] - pref_diff[i] - k);
                max_diff = min(max_diff, k + diff_s[j] - pref_sum[i]);
                k += c;
            }
        }

        int l1 = n, r1 = n, l2 = 0, r2 = 0;
        for (int i = 0; i < n; ++i) {
            while (l1 && x[i] + x[l1 - 1] >= min_sum) {
                --l1;
            }
            while (r1 && x[i] + x[r1 - 1] > max_sum) {
                --r1;
            }
            while (l2 < n && x[i] - x[l2] > max_diff) {
                ++l2;
            }
            while (r2 < n && x[i] - x[r2] >= min_diff) {
                ++r2;
            }
            if (max(l1, l2) < min(r1, r2)) {
                return true;
            }
        }
        return false;
    };

    nth_element(d.begin(), d.begin() + 2, d.end(), greater());
    ll low = d[0] + d[1], high = x[n - 1] + d[0] + d[1];
    while (low + 1 < high) {
        ll mid = (low + high) >> 1;
        if (check(mid)) {
            high = mid;
        } else {
            low = mid;
        }
    }
    return high;
}

• 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