Submission #974074

#	Time	Username	Problem	Language	Result	Execution time	Memory
974074		mariaclara	Shortcut (IOI16_shortcut)	C++17	0 / 100	1 ms	428 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;
#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 find_shortcut(int n, vector<int> l, vector<int> d, int c) {
    vector<ll> p(n,0), v(n);
    for(int i = 1; i < n; i++) p[i] = p[i-1] + l[i-1];
    for(int i = 0; i < n; i++) {
        v[i] = p[i] + d[i];
        if(i and v[i-1] > v[i]) v[i] = v[i-1];
    }
    
    ll L = 0, R = 1e15;
    
    while(L <= R) {
        int 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
        int first_a = n;
        ll max_sufix = 0;
        for(int i = 0; i < n; i++) {
            int left = i, right = n-1;
            while(left <= right) {
                int meio = (left+right)/2;
                if(v[meio] - p[i] + d[i] > mid) right = meio-1;
                else left = meio+1;
            }
            a[i] = right+1;
            if(a[i] < i) a[i] = n;
            first_a = min(first_a, a[i]);
        }

        for(int i = first_a; i < n; i++) max_sufix = max(max_sufix, p[i] + d[i]);

        bool ok = 1;
        for(int i = first_a; i < n; i++)
            if(max_sufix - p[i] + d[i] > mid) ok = 0;

        if(!ok) {
            L = mid+1;
            continue;
        }

        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(all(p), max(B - p[i], p[i] - C)) - p.begin();
            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: 0 / 9
• Subtask 2: 0 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3