제출 #425998

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
425998		jtnydv25	Shortcut (IOI16_shortcut)	C++17	97 / 100	2075 ms	62936 KiB

shortcut

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

#define ll long long
#define all(c) ((c).begin()), ((c).end())
 
#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];
ll p[N];

int perm1[N], perm2[N];
ll add[N], sub[N];

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c){
    int mx = 0, mx2 = 0, ind_mx = 0;
    A[0] = -INF; B[0] = INF;

    for(int i = 0; i < n; i++){
        if(i) p[i] = p[i - 1] + l[i - 1];
        add[i] = p[i] + d[i];
        sub[i] = p[i] - d[i];
    }
    iota(perm1, perm1 + n, 0);
    iota(perm2, perm2 + n, 0);
    sort(perm1, perm1 + n, [&](int i, int j){return sub[i] < sub[j];});
    sort(perm2, perm2 + n, [&](int i, int j){return add[i] < add[j];});

    for(int i = 1; i <= n; i++){
        int ind = perm1[i - 1];
        A[i] = max(A[i - 1], add[ind]);
        B[i] = min(B[i - 1], sub[ind]);
        if(d[ind] > mx){
            mx2 = mx;
            mx = d[ind];
            ind_mx = ind;
        } else if(d[ind] > mx2) mx2 = d[ind];
    }

    ll lo = mx + mx2, hi = p[n - 1] / 2 + 3e9;
    lo = max(lo, (p[n - 1] - 1000000000) / 3);
    
    while(lo < hi){
        ll D = (lo + hi) / 2;
        ll L1 = -INF, R1 = INF;
        ll L2 = -INF, R2 = INF;
        int cur = 0;
        ll V = c - D;
        for(int ind = 0; ind < n; ind++){
            int i = perm2[ind];
            while(cur < n && add[i] - sub[perm1[cur]] > D) cur++;
            ll a = A[cur], b = B[cur];
            if(D < 2 * mx && i == ind_mx){
                a = -INF; b = INF;
                for(int r = 0; r < cur; r++){
                    int _r = perm1[r];
                    if(_r == i) continue;
                    a = max(a, add[_r]);
                    b = min(b, sub[_r]);
                }
            }
            L1 = max(L1, a - sub[i]);
            R1 = min(R1, b - add[i]);
            L2 = max(L2, a + add[i]);
            R2 = min(R2, b + sub[i]);
        }
        L1 += V; L2 += V;
        R1 -= V; R2 -= V;
        if(L1 > R1 || L2 > R2){
            lo = D + 1;
            continue;
        } 

        bool ok = false;

        int ptr1 = 0;
        int ptr2 = n;
        for(int v = 1; v < n; v++){
            while(ptr1 < n && p[ptr1] - p[v] < L1) ptr1++;
            while(ptr2 > 0 && p[ptr2 - 1] + p[v] >= L2) ptr2--;
            int u = max(ptr1, ptr2);
            if(u >= v) continue;
            if(p[u] - p[v] > R1 || p[u] + p[v] > R2) continue;
            ok = true;
            break;
        }
        if(ok) hi = D;
        else lo = D + 1;
    }
    return lo;
}

• 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