Submission #535439

#	Time	Username	Problem	Language	Result	Execution time	Memory
535439		mario05092929	Shortcut (IOI16_shortcut)	C++14	23 / 100	29 ms	4472 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair <ll,ll> pi;
typedef vector <int> vec;
const ll INF = 1e18;
ll p[1000005],d[1000005];
ll di,ans;
int n;
vector <pi> lad,lsu;
int adp[1000005],sup[1000005],adrp[1000005],surp[1000005];
ll ad[1000005],su[1000005];
int t[1 << 20],bit = (1 << 19);

bool cmp_ad(int x,int y) {return ad[x] < ad[y];}

void up(int x,int wi) {
    x += bit;
    t[x] = wi;
    x /= 2;
    while(x) {
        if(su[t[x]] <= su[wi]) break;
        t[x] = wi;
        x /= 2;
    }
}

int query(ll val) {
    int ret = n;
    if(ad[t[1]] > val) return t[1];
    for(int x = 1;x < bit*2;) {
        x *= 2;
        if(ad[t[x+1]] > val) {if(su[ret] > su[t[x+1]]) ret = t[x+1];}
        else x++;
    }
    return ret;
}

bool isok(ll m) {
    ll adl,adr,sul,sur;
    adl = sul = -INF;
    adr = sur = INF;
    for(int i = 1;i < bit*2;i++) t[i] = n;
    int adpo = -1;
    for(int i = n-1;i >= 0;i--) {
        ll v = m+p[i]-d[i];
        if(adpo != -1&&ad[adpo] > v) {
            int j = adpo;
            ll A = p[i], B = p[j], C = m-d[i]-d[j]-di;
            sur = min(sur,A-B+C);
            adl = max(adl,A+B-C);
            j = query(v);
            B = p[j], C = m-d[i]-d[j]-di;
            sul = max(sul,A-B-C);
            adr = min(adr,A+B+C);
            //cout << adpo << ' ' << j << '\n';
            if(adl > adr||sul > sur) return 0;
        }
        if(adpo == -1||adrp[adpo] < adrp[i]) adpo = i;
        up(adrp[i],i);
    }
    //cout << m << " : " << sul << ' ' << sur << ' ' << adl << ' ' << adr << '\n';
    int po = 0;
    for(int i = 0;i < n;i++) {
        ll x = p[i],l,r;
        l = max(adl-x,sul+x), r = min(adr-x,sur+x);
        for(;po >= 1&&p[po-1] >= l;po--);
        for(;po < n&&p[po] < l;po++);
        //cout << po << '\n';
        if(po < n&&p[po] <= r) return 1;
    }
    return 0;
}

ll find_shortcut(int N,vec len,vec dist,int gi) {
    di = gi; n = N;
    //for(bit = 1;bit <= n;bit *= 2);
    ll lm = 0,rm = -INF;
    for(int i = 0;i < n;i++) d[i] = dist[i];
    for(int i = 1;i < n;i++) p[i] = p[i-1]+len[i-1];
    for(int i = 0;i < n;i++) adp[i] = i;
    for(int i = 0;i < n;i++) {
        ad[i] = p[i]+d[i], su[i] = p[i]-d[i];
        lm = max(lm,ad[i]+rm);
        rm = max(rm,-su[i]);
    }
    ad[n] = su[n] = INF;
    sort(adp,adp+n,cmp_ad);
    sort(dist.rbegin(),dist.rend());
    for(int i = 0;i < n;i++) adrp[adp[i]] = i;
    ll l = dist[0]+dist[1], r = lm;
    while(l <= r) {
        //cout << l << ' ' << r <<'\n';
        ll mid = (l + r) >> 1;
        if(isok(mid)) r = mid-1, ans = mid;
        else l = mid+1;
    }
    return ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 14 / 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