oj.uz

Submission #787430

# Submission time Handle Problem Language Result Execution time Memory
787430 2023-07-19T07:33:18 Z fatemetmhr Shortcut (IOI16_shortcut) C++17
0 / 100
 2 ms 2288 KB 
//  ~ 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)
        swap(a, b);
    return d[a] + d[b] + ps[b] - ps[a];
}


pair <ll, int> find_far(int a, int b, int c){
    ll disa = get_dis(a, c) - d[a] - d[c], disb = get_dis(b, c) - d[b] - d[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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2260 KB n = 4, 80 is a correct answer
2 Correct 2 ms 2288 KB n = 9, 110 is a correct answer
3 Correct 1 ms 2284 KB n = 4, 21 is a correct answer
4 Correct 1 ms 2260 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 2260 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2260 KB n = 4, 80 is a correct answer
2 Correct 2 ms 2288 KB n = 9, 110 is a correct answer
3 Correct 1 ms 2284 KB n = 4, 21 is a correct answer
4 Correct 1 ms 2260 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 2260 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2260 KB n = 4, 80 is a correct answer
2 Correct 2 ms 2288 KB n = 9, 110 is a correct answer
3 Correct 1 ms 2284 KB n = 4, 21 is a correct answer
4 Correct 1 ms 2260 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 2260 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2260 KB n = 4, 80 is a correct answer
2 Correct 2 ms 2288 KB n = 9, 110 is a correct answer
3 Correct 1 ms 2284 KB n = 4, 21 is a correct answer
4 Correct 1 ms 2260 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 2260 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2260 KB n = 4, 80 is a correct answer
2 Correct 2 ms 2288 KB n = 9, 110 is a correct answer
3 Correct 1 ms 2284 KB n = 4, 21 is a correct answer
4 Correct 1 ms 2260 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 2260 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2260 KB n = 4, 80 is a correct answer
2 Correct 2 ms 2288 KB n = 9, 110 is a correct answer
3 Correct 1 ms 2284 KB n = 4, 21 is a correct answer
4 Correct 1 ms 2260 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 2260 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2260 KB n = 4, 80 is a correct answer
2 Correct 2 ms 2288 KB n = 9, 110 is a correct answer
3 Correct 1 ms 2284 KB n = 4, 21 is a correct answer
4 Correct 1 ms 2260 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 2260 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2260 KB n = 4, 80 is a correct answer
2 Correct 2 ms 2288 KB n = 9, 110 is a correct answer
3 Correct 1 ms 2284 KB n = 4, 21 is a correct answer
4 Correct 1 ms 2260 KB n = 3, 4 is a correct answer
5 Incorrect 2 ms 2260 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -