Submission #1039045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039045		Wansur	Shortcut (IOI16_shortcut)	C++17	100 / 100	1203 ms	90076 KiB

shortcut

#include <bits/stdc++.h>
#include "shortcut.h"
#define f first
#define s second
#define ent '\n'

typedef long long ll;
using namespace std;
const int maxn = 1e6 + 12;

int L[maxn], prmn[maxn];
int R[maxn], sfmx[maxn];
bool add[maxn];
int posq[maxn];
int p[maxn], q[maxn], l[maxn];
ll mx[maxn], mn[maxn];
ll pref[maxn], d[maxn];
int n, c;

void upd(int i, ll x){
    for(; i <= n; i |= (i + 1)){
        mx[i] = max(mx[i], x);
    }
}

ll get(int i){
    ll Mx = -1e18;
    for(; i > 0; i = (i & (i + 1)) - 1){
        Mx = max(Mx, mx[i]);
    }
    return Mx;
}

bool check2(ll D){
    ll x1 = 0, x2 = 1e18, y1 = 0, y2 = 1e18;
    for(int i=0;i<=n;i++){
        mx[i] = -1e18;
    }
    for(int i=1, j=0;i<=n;i++){
        while(j < n && pref[p[j+1]] - d[p[j+1]] < pref[q[i]] + d[q[i]] - D){
            j++;
            upd(p[j], pref[p[j]] + d[p[j]]);
            add[p[j]] = 1;
        }
        ll mx = get(q[i]-1);
        ll x = p[L[q[i]]], mn = pref[x] - d[x];
        if(mn >= 1e17 || mn >= pref[q[i]] + d[q[i]] - D) continue;
        ll ly = mx + d[q[i]] + c - D, ry = mn + D - d[q[i]] - c;
        x2 = min(x2, pref[q[i]] + ry);
        y1 = max(y1, pref[q[i]] - ry), y2 = min(y2, pref[q[i]] - ly);
    }
    for(int i=n;i;i--){
        ll x = q[R[p[i]]], mx = pref[x] + d[x];
        if(mx > pref[p[i]] - d[p[i]] + D && x > p[i]){
            x1 = max(x1, mx + pref[p[i]] + d[p[i]] + c - D);
        }
    }
    if(x1 > x2 || y1 > y2) return 0;
    for(int i=n, j = 1;i;i--){
        while(j <= n && x1 - pref[i] > pref[j]){
            j++;
        }
        l[i] = j;
    }
    for(int i=1, j=1;i<=n;i++){
        while(j <= n && pref[i] - y2 > pref[j]){
            j++;
        }
        l[i] = max(l[i], j);
        if(l[i] < i && y1 <= pref[i] - pref[l[i]] && pref[i] - pref[l[i]] <= y2 && x1 <= pref[i] + pref[l[i]] && pref[i] + pref[l[i]] <= x2){
            return 1;
        }
    }
    return 0;
}

bool check(ll D){
    if(n <= 3e5){
        return check2(D);
    }
    ll x1 = 0, x2 = 1e18, y1 = 0, y2 = 1e18;
    for(int i=1;i<=n;i++){
        ll x = q[R[i]], mx = pref[x] + d[x];
        if(mx > pref[i] - d[i] + D && x > i){
            x1 = max(x1, mx + pref[i] + d[i] + c - D);
            y2 = min(y2, pref[x] - pref[i] - d[i] - d[x] - c + D);
        }
        x = p[L[i]];
        ll mn = pref[x] - d[x];
        if(mn >= 1e17 || mn >= pref[i] + d[i] - D) continue;
        ll ry = mn + D - d[i] - c;
        x2 = min(x2, pref[i] + ry);
        y1 = max(y1, pref[i] - ry);
    }
    for(int t=1, j = 0;t<=n;t++){
        int i = q[t];
        int x = 0, y = 0;
        while(pref[p[j+1]] - d[p[j+1]] < pref[i] + d[i] - D){
            j++;
            if(pref[p[j]] + d[p[j]] > pref[x] + d[x] || x == 0){
                y = x;
                x = p[j];
            }
            else if(pref[p[j]] + d[p[j]] > pref[y] + d[y] || y == 0){
                y = p[j];
            }
        }
        if(x != i){
            if(x != 0) {
                y2 = min(y2, pref[i] - pref[x] - d[x] - d[i] - c + D);
                x1 = max(x1, pref[i] + pref[x] + d[x] + d[i] + c - D);
            }
        }
        else{
            if(y != 0) {
                y2 = min(y2, pref[i] - pref[y] - d[y] - d[i] - c + D);
                x1 = max(x1, pref[i] + pref[y] + d[y] + d[i] + c - D);
            }
        }
    }
    if(x1 > x2 || y1 > y2) return 0;
    for(int i=n, j = 1;i;i--){
        while(j <= n && x1 - pref[i] > pref[j]){
            j++;
        }
        l[i] = j;
    }
    for(int i=1, j=1;i<=n;i++){
        while(j <= n && pref[i] - y2 > pref[j]){
            j++;
        }
        l[i] = max(l[i], j);
        if(l[i] < i && y1 <= pref[i] - pref[l[i]] && pref[i] - pref[l[i]] <= y2 && x1 <= pref[i] + pref[l[i]] && pref[i] + pref[l[i]] <= x2){
            return 1;
        }
    }
    return 0;
}

ll find_shortcut(int N, vector<int> l, vector<int> D, int C){
    n = N, c = C;
    for(int i=2;i<=n;i++){
        pref[i] = pref[i-1] + l[i-2];
    }
    for(int i=1;i<=n;i++){
        d[i] = D[i-1];
        p[i] = i;
        q[i] = i;
    }
    sort(p+1, p+n+1, [](int i, int j){
        return pref[i] - d[i] < pref[j] - d[j];
    });
    sort(q+1, q+n+1, [](int i, int j){
        return pref[i] + d[i] < pref[j] + d[j];
    });
    prmn[0] = 1e9;
    for(int i=1;i<=n;i++){
        prmn[i] = min(prmn[i-1], p[i]);
    }
    sfmx[n+1] = -1e9;
    for(int i=n;i;i--){
        sfmx[i] = max(sfmx[i+1], q[i]);
    }
    p[n+1] = n + 1;
    pref[n+1] = 1e18;
    pref[0] = -1e18;
    for(int i=1;i<=n;i++){
        L[i] = n + 1, R[i] = 0;
        for(int l=1, r=n;l<=r;){
            int mid = l + r >> 1;
            if(prmn[mid] < i){
                L[i] = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        for(int l=1, r=n;l<=r;){
            int mid = l + r >> 1;
            if(sfmx[mid] > i){
                R[i] = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
    }
    ll ans = 0;
    for(ll l = 0, r = 1e15 + 2e9; l <= r;){
        ll mid = l + r >> 1;
        bool c = 0;
        if(r - l + 1 <= 100){
            c = check2(mid);
        }
        else{
            c = check(mid);
        }
        if(c){
            ans = mid;
            r = mid - 1;
        }
        else{
            l = mid + 1;
        }
    }
    return ans;
}

Compilation message (stderr)

shortcut.cpp: In function 'll find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:170:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  170 |             int mid = l + r >> 1;
      |                       ~~^~~
shortcut.cpp:178:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  178 |             int mid = l + r >> 1;
      |                       ~~^~~
shortcut.cpp:188:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  188 |         ll mid = l + 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: 3 / 3