Submission #787435

#	Time	Username	Problem	Language	Result	Execution time	Memory
787435		fatemetmhr	Shortcut (IOI16_shortcut)	C++17	0 / 100	2 ms	2260 KiB

shortcut

//  ~ Be Name Khoda ~  //

#include "shortcut.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  3e3   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const int lg    =  20;
const ll  inf   =  1e18;

int n;
ll c;
vector <ll> d;
ll ps[maxn5], ps2[maxn5];

pair<ll, int> operator +(pair <ll, int> x, ll a){
    return mp(x.fi + a, x.se);
}

pair<ll, int> operator -(pair <ll, int> x, ll a){
    return mp(x.fi - a, x.se);
}

struct RMQ{

    int n;
    pair <ll, int> mx[lg + 1][maxn5];
    void build(int N){
        n = N;
        for(int j = 1; j < lg; j++)
            for(int i = 0; i < n; i++)
                mx[j][i] = max(mx[j - 1][i], (i + (1 << (j - 1)) < n ? mx[j - 1][i + (1 << (j - 1))] : mp(0ll, 0)));

    }

    pair <ll, int> get(int l, int r){
        if(l > r)
            return {0, 0};
        int k = 31 - __builtin_clz(r - l + 1);
        return max(mx[k][l], mx[k][r - (1 << k) + 1]);
    }

} seg1, seg2;

ll get_dis(int a, int b){
    if(a == b)
        return 0;
    if(a > b)
        swap(a, b);
    return ps[b] - ps[a];
}


pair <ll, int> find_far(int a, int b, int c){
    ll disa = get_dis(a, c), disb = get_dis(b, c);
    //cout << "Wat " << a << ' ' << b << ' ' << c << ' ' << disa << ' ' << disb << endl;
    disa = min(disa, disb + ::c);
    disb = min(disb, disa + ::c);
    int lo = -1, hi = c;
    while(hi - lo > 1){
        int mid = (lo + hi) >> 1;
        if(get_dis(mid, c) <= min(get_dis(a, mid) + disa, get_dis(b, mid) + disb))
            hi = mid;
        else
            lo = mid;
    }
    int ptl = hi;
    lo = c; hi = n;
    while(hi - lo > 1){
        int mid = (lo + hi) >> 1;
        //cout << "check " << mid << ' ' << disa << ' ' << disb << endl;
        if(get_dis(mid, c) <= min(get_dis(a, mid) + disa, get_dis(b, mid) + disb))
            lo = mid;
        else
            hi = mid;
    }
    int ptr = lo;
    lo = -1; hi = n;
    while(hi - lo > 1){
        int mid = (lo + hi) >> 1;
        if(get_dis(mid, a) + disa <= get_dis(mid, b) + disb)
            lo = mid;
        else
            hi = mid;
    }
    pair <ll, int> mx = {0, c};
    mx = max(mx, seg2.get(ptl, c) - ps2[c]);
    mx = max(mx, seg1.get(c, ptr) - ps[c]);
    //cout << mx.fi << ' ' << mx.se << endl;
    if(lo >= 0)
        mx = max(mx, seg2.get(0, min(lo, a)) + disa - ps2[a]);
    if(lo > a)
        mx = max(mx, seg1.get(a, lo) + disa - ps[a]);
    //cout << mx.fi << ' ' << mx.se << endl;
    if(hi < n)
        mx = max(mx, seg1.get(max(hi, b), n - 1) + disb - ps[b]);
    //cout << mx.fi << ' ' << mx.se << ' ' << disb << ' ' << ps2[b] << endl;
    if(hi < b)
        mx = max(mx, seg2.get(hi, b) + disb - ps2[b]);
    //cout << "ok " << a << ' ' << b << ' ' << c << ' ' << ptl << ' ' << ptr << ' ' << lo << ' '  << mx.fi << ' ' << mx.se << endl;
    mx = mx + d[c];
    return mx;
}

ll get_dim(int a, int b){
    auto ans1 = find_far(a, b, 0);
    auto ans2 = find_far(a, b, ans1.se);
    return ans2.fi;
}

long long find_shortcut(int N, std::vector<int> l, std::vector<int> D, int C)
{
    n = N;
    c = C;
    for(auto u : D)
        d.pb(u);
    ps[0] = 0;
    for(int i = 1; i < n; i++)
        ps[i] = ps[i - 1] + l[i - 1];
    ps2[n - 1] = 0;
    for(int i = n - 2; i >= 0; i--)
        ps2[i] = ps2[i + 1] + l[i];
    //*
    for(int i = 0; i < n; i++){
        seg1.mx[0][i] = {d[i] + ps[i], i};
        seg2.mx[0][i] = {d[i] + ps2[i], i};
    }
    seg1.build(n);
    seg2.build(n);
    //*/
    ll mn = inf;
    for(int i = 0; i < n; i++)
        for(int j = i + 1; j < n; j++)
            mn = min(mn, get_dim(i, j));
    return mn;
}

• 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