Submission #1207904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207904		garam1732	Shortcut (IOI16_shortcut)	C++20	93 / 100	2095 ms	21676 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 = 2e9;

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

vector<ll> v;
int sz;

struct MinSeg {
    ll tree[MAXN*4];

    void init() {
        fill(tree, tree+4*N, LLONG_MAX);
    }

    void update(int node, int s, int e, int idx, ll val) {
        if(idx < s || e < idx) return;
        if(s == e) {
            tree[node] = min(tree[node], val);
            return;
        }

        int mid = s+e>>1;
        update(node<<1, s, mid, idx, val); update(node<<1|1, mid+1, e, idx, val);
        tree[node] = min(tree[node<<1], tree[node<<1|1]);
    }

    ll solve(int node, int s, int e, int l, int r) {
        if(e < l || r < s) return LLONG_MAX;
        if(l <= s && e <= r) return tree[node];

        int mid = s+e>>1;
        return min(solve(node<<1, s, mid, l, r), solve(node<<1|1, mid+1, e, l, r));
    }
} mnseg;

bool solve(ll L) {
    ll mnsum, mxsum, mndif, mxdif;
    mnsum = mndif = LLONG_MIN, mxsum = mxdif = LLONG_MAX;
    mnseg.init(); ll mx = LLONG_MIN;
    for(int i=N-2; i>=0; i--) {
        int it = lbd(v, sum[i+1]+w[i+1]);
        mx = max(mx, sum[i+1]+w[i+1]);
        mnseg.update(1, 0, sz-1, it, sum[i+1]-w[i+1]);
        
        it = ubd(v, L+sum[i]-w[i]);
        ll mn = mnseg.solve(1, 0, sz-1, it, sz-1);
        if(mn != LLONG_MAX) {
            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]);
            mx -= -L+w[i]+C;
        }
    }

    for(int i=0; i<N-1; i++) {
        ll mn = max(mnsum-sum[i], mndif+sum[i]);
        ll mx = min(mxsum-sum[i], mxdif+sum[i]);
        
        int it = lower_bound(sum+i+1, sum+N, mn)-sum;
        if(it < N && sum[it] <= mx) 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(w[i]+sum[i]);
    sort(all(v)); comp(v); sz = v.size();

    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: 0 / 4
• Subtask 8: 0 / 3