Submission #1207992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207992		garam1732	Shortcut (IOI16_shortcut)	C++20	100 / 100	1852 ms	114068 KiB

shortcut

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

#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;

const int MAXN = 100100*10;
const ll MOD = 998244353;
const ll INF = 1e16;

ll sum[MAXN], w[MAXN];
int N, C;

vector<pll> v, u;
int sz;

pll mx1 = {-INF, 0}, mx2 = {-INF, 0};
pll mn1[MAXN], mn2[MAXN];

int it[MAXN];
int l1[MAXN], r1[MAXN], l2[MAXN], r2[MAXN];

bool solve(ll L) {
    ll mnsum, mxsum, mndif, mxdif;
    mnsum = mndif = -INF, mxsum = mxdif = INF;

    for(int i=N-1, j=N; i>=0; i--) {
        while(j && v[j-1].ff > u[i].ff+L) j--;
        it[u[i].ss] = j;
    }

    for(int i=N-1; i>=0; i--) {
        int x = it[i];
        ll mn = (mn1[x].ss == i ? mn2[x].ff : mn1[x].ff);
        ll mx = (mx1.ss == i ? mx2.ff : mx1.ff);
        if(mn != INF && mx > L+sum[i]-w[i]) {
            mn += L-w[i]-C; mx += -L+w[i]+C;
            mnsum = max(mnsum, sum[i]+mx); mxsum = min(mxsum, sum[i]+mn);
            mndif = max(mndif, mx-sum[i]); mxdif = min(mxdif, mn-sum[i]);
        }
    }

    for(int i=0, j=N; i<N; i++) {
        while(j && mnsum <= sum[i]+sum[j-1]) j--;
        l1[i] = j; 
    } for(int i=N-1, j=-1; i>=0; i--) {
        while(j+1<N && sum[i]+sum[j+1] <= mxsum) j++;
        r1[i] = j;
    } for(int i=N-1, j=N; i>=0; i--) {
        while(j && mndif <= sum[j-1]-sum[i]) j--;
        l2[i] = j;
    } for(int i=0, j=-1; i<N; i++) {
        while(j+1<N && sum[j+1]-sum[i] <= mxdif) j++;
        r2[i] = j;
    }

    for(int i=0; i<N-1; i++) {
        if(max(max(l1[i], l2[i]), i+1) <= min(r1[i], r2[i])) return true;
    } return false;
}

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
    for(int i=1; i<n; i++) sum[i] = sum[i-1]+l[i-1];
    for(int i=0; i<n; i++) w[i]=d[i];
    N = n, C = c;

    for(int i=0; i<n; i++) v.push_back(pll(w[i]+sum[i], i));
    for(int i=0; i<n; i++) u.push_back(pll(sum[i]-w[i], i));
    sort(all(v)); sort(all(u));

    for(int i=0; i<N; i++) {
        if(mx2.ff < sum[i]+w[i]) mx2 = pll(sum[i]+w[i], i);
        if(mx1 < mx2) swap(mx1, mx2);
    }

    mn1[N] = mn2[N] = pll(INF, 0);
    for(int i=N-1; i>=0; i--) {
        mn1[i] = mn1[i+1]; mn2[i] = mn2[i+1];
        
        int x = v[i].ss;
        if(mn2[i].ff > sum[x]-w[x]) mn2[i] = pll(sum[x]-w[x], x);
        if(mn1[i] > mn2[i]) swap(mn1[i], mn2[i]);
    }

    ll lb = 0, ub = 1e16, mid;
    while(lb < ub) {
        mid = lb+ub>>1;

        if(solve(mid)) ub = mid;
        else lb = mid+1;
    }

	return lb;
}

Compilation message (stderr)

shortcut.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• 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