Submission #915352

#	Time	Username	Problem	Language	Result	Execution time	Memory
915352		vjudge1	Shortcut (IOI16_shortcut)	C++17	0 / 100	1 ms	6492 KiB

shortcut

#include "shortcut.h"

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

const int N = 1e6;
int64_t a[N], b[N], x[N];
int orda[N], ordb[N];
int n, c;
pair<int, int> max_a(-1, -1), min_b(-1, -1);

int64_t get(int64_t o[], const pair<int, int>& v, const int& j, const int64_t& inf) {
        if (v.first == -1) return inf;
        if (v.first == j) return v.second == -1 ? inf : o[v.second];
        return o[v.first];
};

inline void update(const int& j) {
        if (max_a.first == -1 || a[j] >= a[max_a.first]) {
                max_a.second = max_a.first;
                max_a.first = j;
        } else if (max_a.second == -1 || a[j] > a[max_a.second]) {
                max_a.second = j;
        }

        if (min_b.first == -1 || b[j] <= b[min_b.first]) {
                min_b.second = min_b.first;
                min_b.first = j;
        } else if (min_b.second == -1 || b[j] < b[min_b.second]) {
                min_b.second = j;
        }
};

inline bool check(const int64_t& target) {
        int64_t low_sum = -1e18, high_sum = +1e18;
        int64_t low_diff = -1e18, high_diff = +1e18;
        const int64_t k = c - target;
        max_a = min_b = make_pair(-1, -1);
        int i = 0;

        for (int z = 0; z < n; z++) {
                int j = orda[z];
                while (i < n && a[j] - b[ordb[i]] > target) update(ordb[i++]);
                low_sum = max(low_sum, a[j] + get(a, max_a, j, -1e18) + k);
                high_sum = min(high_sum, b[j] + get(b, min_b, j, +1e18) - k);
                low_diff = max(low_diff, a[j] - get(b, min_b, j, +1e18) + k);
                high_diff = min(high_diff, b[j] - get(a, max_a, j, -1e18) - k);
                if (low_sum > high_sum || low_diff > high_diff) return 0;
        }

        int low_sum_q = n - 1, low_diff_q = 0, high_sum_q = n - 1, high_diff_q = 0;
        for (int p = 0; p < n; p++) {
                low_diff_q = max(low_diff_q, p + 1);
                while (low_sum_q > p && x[p] + x[low_sum_q] >= low_sum) low_sum_q--;
                while (high_sum_q > p && x[p] + x[high_sum_q] > high_sum) high_sum_q--;
                // (low_sum_q, high_sum_q]
                while (low_diff_q < n && x[low_diff_q] - x[p] < low_diff) low_diff_q++;
                high_diff_q = max(high_diff_q, low_diff_q);
                while (high_diff_q < n && x[high_diff_q] - x[p] <= high_diff) high_diff_q++;
                // [low_diff_q, high_diff_q)

                low_sum_q = max(low_sum_q, p);
                if (low_sum_q >= high_sum_q && low_sum_q == p) return 0;
                if (low_diff_q >= high_diff_q && high_diff_q == n) return 0;
                if (low_sum_q >= high_sum_q || low_diff_q >= high_diff_q) return 0;
                int max_l = max(low_sum_q + 1, low_diff_q);
                int min_r = min(high_sum_q, high_diff_q - 1);
                if (max_l <= min_r) {
                        return 1;
                }
        }

        return 0;
};

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int 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++) a[i] = x[i] + d[i], b[i] = x[i] - d[i];

        // abs(x[i] - x[p]) + abs(x[j] - x[q]) + d[i] + d[j] + c <= target
        // x[i] - x[p] + x[j] - x[q] + d[i] + d[j] + c <= target
        // x[p] - x[i] + x[j] - x[q] + d[i] + d[j] + c <= target
        // x[i] - x[p] + x[q] - x[j] + d[i] + d[j] + c <= target
        // x[p] - x[i] + x[q] - x[j] + d[i] + d[j] + c <= target

        // x[p] + x[q] >= x[i] + x[j] + d[i] + d[j] + c - target
        // x[p] + x[q] <= x[i] + x[j] - d[i] - d[j] - c + target
        // x[q] - x[p] <= x[j] - x[i] - d[i] - d[j] - c + target
        // x[q] - q[p] >= x[j] - x[i] + d[i] + d[j] + c - target

        // k := c - target
        // x[p] + x[q] >= (x[i] + d[i]) + (x[j] + d[j]) + k
        // x[p] + x[q] <= (x[i] - d[i]) + (x[j] - d[j]) - k
        // x[q] - x[p] <= (x[j] - d[j]) - (x[i] + d[i]) - k
        // x[q] - x[p] >= (x[j] + d[j]) - (x[i] - d[i]) + k

        // x[p] + x[q] >= a[i] + a[j] + k
        // x[p] + x[q] <= b[i] + b[j] - k
        // x[q] - x[p] <= b[j] - a[i] - k
        // x[q] - x[p] >= a[j] - b[i] + k

        iota(orda, orda + n, 0);
        sort(orda, orda + n, [&](int i, int j) { return a[i] < a[j]; });
        iota(ordb, ordb + n, 0);
        sort(ordb, ordb + n, [&](int i, int j) { return b[i] < b[j]; });

        int64_t low = 1, high = 1e15 + 2e9;
        while (low < high) {
                int64_t mid = low + high >> 1;
                if (check(mid)) {
                        high = mid;
                } else {
                        low = mid + 1;
                }
        }
        return high;
}

Compilation message (stderr)

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:110:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |                 int64_t mid = low + high >> 1;
      |                               ~~~~^~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3