Submission #423681

#	Time	Username	Problem	Language	Result	Execution time	Memory
423681		jtnydv25	Shortcut (IOI16_shortcut)	C++17	93 / 100	2086 ms	28364 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())

#ifdef LOCAL
#include <print.h>
#else
#define trace(...)
#define endl '\n'
#endif
const int N = 1 << 20;
const ll INF = 1e18;
ll A[N], B[N];

void init(){
    fill(A, A + N, -INF);
    fill(B, B + N, INF);
}

inline void add(int j, ll x, ll y){
    int i = j + 1;
    for(; i < N; i += i & -i)
        A[i] = max(A[i], x);
    for(i = j + 1; i < N; i += i & -i)
        B[i] = min(B[i], y);
}

ll tempa, tempb;

void get(int j){
    int i = j + 1;
    tempa = -INF;
    tempb = INF;
    for(; i; i -= i & -i)
        tempa = max(tempa, A[i]);
    for(i = j + 1; i; i -= i & -i)
        tempb = min(tempb, B[i]);
}

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c){
    vector<ll> p(n);
    for(int i = 1; i < n; i++) p[i] = p[i - 1] + l[i - 1];
    vector<int> perm1(n), perm2(n);
    vector<int> where(n);
    iota(all(perm1), 0);
    iota(all(perm2), 0);
    sort(all(perm1), [&](int i, int j){return d[i] - p[i] > d[j] - p[j];});
    sort(all(perm2), [&](int i, int j){return d[i] + p[i] < d[j] + p[j];});

    for(int i = 0; i < n; i++) where[perm1[i]] = i;

    ll lo = 0, hi = 1000000000LL * 10000000LL;
    vector<int> position(n);
    while(lo < hi){
        ll D = (lo + hi) / 2;
        int cur = 0; // < 0
        for(int i : perm2){
            while(cur < n && d[perm1[cur]] + d[i] + p[i] - p[perm1[cur]] > D) cur++;
            position[i] = cur;
        }
        init();
        ll L1 = -INF, R1 = INF, L2 = -INF, R2 = INF;
        for(int j = 0; j < n; j++){
            get(position[j] - 1);
            L1 = max(L1, tempa + d[j] + c - p[j] - D);
            R1 = min(R1, tempb - d[j] - c - p[j] + D);
            L2 = max(L2, tempa + p[j] - D + d[j] + c);
            R2 = min(R2, tempb + p[j] + D - d[j] - c);
            add(where[j], p[j] + d[j], p[j] - d[j]);
        }

        if(L1 > R1 || L2 > R2){
            lo = D + 1;
            continue;
        } 
        // some u, v with p[u] - p[v] in [L1, R1] and p[u] + p[v] in [L2, R2]
        bool ok = false;
        int ptr1 = 0; // first >= p[v] + L1
        int ptr2 = n; // first >= L2 - p[v];
        for(int v = 1; v < n; v++){
            ll L = max(p[v] + L1, L2 - p[v]);
            ll R = min(p[v] + R1, R2 - p[v]);
            // in L, R?
            // int u = upper_bound(all(p), L - 1) - p.begin(); // first >= L
            while(ptr1 < n && p[ptr1] < L1 + p[v]) ptr1++;
            while(ptr2 > 0 && p[ptr2 - 1] >= L2 - p[v]) ptr2--;
            int u = max(ptr1, ptr2);

            if(u >= v) continue;
            if(p[u] > R) continue;
            ok = true;
            break;
        }
        if(ok) hi = D;
        else lo = D + 1;
    }
    return lo;
}

Compilation message (stderr)

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:85:16: warning: unused variable 'L' [-Wunused-variable]
   85 |             ll L = max(p[v] + L1, L2 - p[v]);
      |                ^

• 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