Submission #1239323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239323		Zbyszek99	Shortcut (IOI16_shortcut)	C++20	100 / 100	1641 ms	86648 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

ll P[1000001];
ll D[1000001];
ll C;
int n;
vector<pll> vsort1;
vector<pll> vsort2;
pii bor1[1000001];
pii bor2[1000001];

pll max2(pll x, ll val)
{
    if(val >= x.ff)
    {
        swap(x.ff,x.ss);
        x.ff = val;
    }
    else if(val >= x.ss)
    {
        x.ss = val;
    }
    return x;
}

pll min2(pll x, ll val)
{
    if(val <= x.ff)
    {
        swap(x.ff,x.ss);
        x.ff = val;
    }
    else if(val <= x.ss)
    {
        x.ss = val;
    }
    return x;
}

bool check(ll K)
{
    ll left_plus = -1e18;
    ll right_plus = 1e18;
    ll left_minus = -1e18;
    ll right_minus = 1e18;
    pll cur_max_sum = {-1e18,-1e18};
    pll cur_min_dif = {1e18,1e18};
    pll cur_max_dif = {-1e18,-1e18};
    pll cur_min_sum = {1e18,1e18};
    int cur_vsort2 = 0;
    forall(it,vsort1)
    {
        while(cur_vsort2 < siz(vsort2) && vsort2[cur_vsort2].ff + it.ff > K)
        {
            int v = vsort2[cur_vsort2].ss;
            cur_vsort2++;
            cur_max_sum = max2(cur_max_sum,P[v]+D[v]);
            cur_min_dif = min2(cur_min_dif,P[v]-D[v]);
            cur_max_dif = max2(cur_max_dif,-P[v]+D[v]);
            cur_min_sum = min2(cur_min_sum,-P[v]-D[v]);
        }
        int v = it.ss;
        left_plus = max(left_plus,(P[v]+D[v] != cur_max_sum.ff ? cur_max_sum.ff : cur_max_sum.ss)+P[v]+D[v]+C-K);
        right_plus = min(right_plus,(P[v]-D[v] != cur_min_dif.ff ? cur_min_dif.ff : cur_min_dif.ss)+P[v]-D[v]-C+K);
        left_minus = max(left_minus,(-P[v]+D[v] != cur_max_dif.ff ? cur_max_dif.ff : cur_max_dif.ss)+P[v]+D[v]+C-K);
        right_minus = min(right_minus,(-P[v]-D[v] != cur_min_sum.ff ? cur_min_sum.ff : cur_min_sum.ss)+P[v]-D[v]-C+K);
    }
    if(left_plus > right_plus || left_minus > right_minus) return 0;
    int min_plus = n-1;
    int max_plus = n-1;
    int min_dif = n-1;
    int max_dif = n-1;
    rep(i,n)
    {
        while(min_plus > 0 && P[min_plus-1] + P[i] >= left_plus)
        {
            min_plus--;
        }
        while(max_plus >= 0 && P[max_plus] + P[i] > right_plus)
        {
            max_plus--;
        }
        bor1[i] = {min_plus,max_plus};
    }
    for(int i = n-1; i >= 0; i--)
    {
        while(min_dif >= 0&& P[i] - P[min_dif] < left_minus)
        {
            min_dif--;
        }
        while(max_dif > 0 && P[i] - P[max_dif-1] <= right_minus)
        {
            max_dif--;
        }
        bor2[i] = {max_dif,min_dif};
    }
    rep(i,n)
    {
        if(bor1[i].ff > bor1[i].ss || bor2[i].ff > bor2[i].ss) continue;
        int l2 = max(bor1[i].ff,bor2[i].ff);
        int r2 = min(bor1[i].ss,bor2[i].ss);
        if(l2 <= r2 && r2 >= 0)
        {
            return 1;
        }
    }
    return 0;
}

ll find_shortcut(int N, vi L, vi d, int c)
{
    n = N;
    C = c;
    ll sum = 0;
    vl Ds;
    rep(i,n)
    {
        Ds.pb(d[i]);
        D[i] = d[i];
        P[i] = sum;
        sum += L[i];
        vsort1.pb({P[i]+D[i],i});
        vsort2.pb({-P[i]+D[i],i});
    }
    sort(all(vsort1));
    sort(all(vsort2));
    reverse(all(vsort2));
    sort(all(Ds));
    reverse(all(Ds));
    ll l = Ds[0]+Ds[1];
    ll r = 1e9*(ll)(n+2);
    ll ans = 0;
    while(l <= r)
    {
        ll mid = (l+r)/2;
        if(check(mid))
        {
            ans = mid;
            r = mid-1;
        }
        else
        {
            l = mid+1;
        }
    }
    return ans;
}

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