Submission #974085

#	Time	Username	Problem	Language	Result	Execution time	Memory
974085		mariaclara	Shortcut (IOI16_shortcut)	C++17	97 / 100	2019 ms	106136 KiB

shortcut

#include "shortcut.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const ll LINF = 1e18;
const int MAXN = 1e6+5;
#define sz(x) x.size()
#define all(x) x.begin(), x.end()
#define mk make_pair 
#define pb push_back
#define f first
#define s second

ll seg[4*MAXN], p[MAXN], d_aux[MAXN];

void build(int node, int l, int r) {
    if(l == r) {
        seg[node] = p[l] + d_aux[l];
        return;
    }
    int mid = (l+r)/2;
    build(2*node, l, mid);
    build(2*node+1, mid+1, r);
    seg[node] = max(seg[2*node], seg[2*node+1]);
}

int query(int node, int l, int r, int i, ll x) {
    if(r < i or seg[node] <= x) return -1;
    if(l == r) return l;
    int mid = (l+r)/2;
    int a = -1;
    if(seg[2*node] > x) a = query(2*node, l, mid, i, x);
    if(a != -1) return a;
    else return query(2*node+1, mid+1, r, i, x);
}

ll find_shortcut(int n, vector<int> l, vector<int> d, int c) {
    for(int i = 1; i < n; i++) p[i] = p[i-1] + l[i-1];
    for(int i = 0; i < n; i++) d_aux[i] = d[i];
    build(1, 0, n-1);
    
    ll L = 0, R = 1e15;
    
    while(L <= R) {
        ll mid = (L+R)/2; // checa se a resposta pode ser menor ou igual a mid

        vector<int> a(n); // a[i] é o primeiro cara tal que p[a[i]] - p[i] + d[a[i]] + d[i] > mid
        for(int i = 0; i < n; i++) {
            a[i] = query(1, 0, n-1, i+1, mid + p[i] - d[i]);
            if(a[i] == -1) a[i] = n;
        }

        vector<ll> maxsum(n+1), maxdif(n+1), minsum(n+1), mindif(n+1);
        maxsum[n] = maxdif[n] = LINF;
        minsum[n] = mindif[n] = -LINF;
        for(int i = n-1; i >= 0; i--) {
            maxsum[i] = min(maxsum[i+1], p[i] + mid - d[i] - c);
            minsum[i] = max(minsum[i+1], p[i] - mid + d[i] + c);
            maxdif[i] = min(maxdif[i+1], -p[i] + mid - d[i] - c);
            mindif[i] = max(mindif[i+1], -p[i] - mid + d[i] + c);
        }

        ll A = LINF, B = -LINF, C = LINF, D = -LINF;
        for(int i = 0; i < n; i++) {
            A = min(A, maxsum[a[i]] + p[i] - d[i]);
            B = max(B, minsum[a[i]] + p[i] + d[i]);
            C = min(C, maxdif[a[i]] + p[i] - d[i]);
            D = max(D, mindif[a[i]] + p[i] + d[i]);
        }

        // basta achar l, r tal que
        // B <= p[l] + p[r] <= A
        // D <= p[l] - p[r] <= C
        // max(B - p[l], p[l] - C) <= p[r] <= min(A - p[l], p[l] - D)

        bool poss_ans = 0;
        for(int i = 0; i < n; i++) { // l fixo
            int ind = lower_bound(p, p+n, max(B - p[i], p[i] - C)) - p;
            if(ind < n and p[ind] <= min(A - p[i], p[i] - D)) poss_ans = 1;
        }

        if(poss_ans) R = mid-1;
        else L = mid+1;
    }

    return R+1;
}

• 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