oj.uz

Submission #436405

# Submission time Handle Problem Language Result Execution time Memory
436405 2021-06-24T13:20:06 Z 79brue Shortcut (IOI16_shortcut) C++14
0 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>
#include "shortcut.h"

using namespace std;

typedef long long ll;

ll minCost(vector<int> v){
    sort(v.rbegin(), v.rend());
    return v[0] + v[1];
}

int n;
ll cost;
ll arr[1000002];
ll loc[1000002];

ll vec[1000002];
ll vec2[1000002];
ll maxXpd;

bool able(ll);

ll find_shortcut(int N, vector<int> l, vector<int> d, int C){
    n = N;
    for(int i=1; i<=n; i++) arr[i] = d[i-1];
    for(int i=2; i<=n; i++) loc[i] = loc[i-1] + l[i-2];
    cost = C;

    for(int i=1; i<=n; i++) vec[i] = vec2[i] = i, maxXpd = max(maxXpd, arr[i] + loc[i]);
    sort(vec+1, vec+n+1, [&](int a, int b){
        return arr[a] + loc[a] > arr[b] + loc[b];
    });
    sort(vec2+1, vec2+n+1, [&](int a, int b){
        return loc[a] - arr[a] > loc[b] - arr[b];
    });

    ll MIN = minCost(d), MAX = 1e18, ANS = 1e18;
    while(MIN <= MAX){
        ll MID = (MIN + MAX) / 2;
        if(able(MID)){
            ANS = MID;
            MAX = MID-1;
        }
        else MIN = MID+1;
    }
    return ANS;
}

bool able(ll X){
    ll minPlus = -1e18, maxPlus = 1e18;
    ll minMinus = -1e18, maxMinus = 1e18;

    int pnt = 1;
    ll minXmd = 1e18;
    for(int i=1; i<=n; i++){
        int x = vec2[i];
        while(pnt <= n && arr[vec[pnt]] + loc[vec[pnt]] > X + loc[x] - arr[x]){
            minXmd = min(minXmd, loc[vec[pnt]] - arr[vec[pnt]]);
            pnt++;
        }

        if(pnt==1) continue;
        maxPlus = min(maxPlus, loc[x] - arr[x] + X + minXmd - cost);
        minPlus = max(minPlus, loc[x] + arr[x] - X + maxXpd + cost);
        maxMinus = min(maxMinus, -loc[x] - arr[x] + X + minXmd - cost);
        minMinus = max(minMinus, -loc[x] + arr[x] - X + maxXpd + cost);
    }

    int pL = n+1, pR = n;
    int mL = 1, mR = 0;
    for(int i=1; i<=n; i++){
        while(pL > 1 && loc[pL-1] + loc[i] >= minPlus) pL--;
        while(pR && loc[pR] + loc[i] > maxPlus) pR--;
        while(mL <= n && loc[i] - loc[mL] < minMinus && mL < i) mL++;
        while(mR <= n && loc[i] - loc[mR+1] <= maxMinus && mR < i) mR++;

        if(pL > pR || mL > mR) continue;
        if(pR < mL || mR < pL) continue;
        return true;
    }
    return false;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 332 KB n = 4, 21 is a correct answer
4 Correct 1 ms 332 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 332 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 1 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 332 KB n = 4, 21 is a correct answer
4 Correct 1 ms 332 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 332 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 1 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 332 KB n = 4, 21 is a correct answer
4 Correct 1 ms 332 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 332 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 1 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 332 KB n = 4, 21 is a correct answer
4 Correct 1 ms 332 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 332 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 1 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 332 KB n = 4, 21 is a correct answer
4 Correct 1 ms 332 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 332 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 1 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 332 KB n = 4, 21 is a correct answer
4 Correct 1 ms 332 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 332 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 1 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 332 KB n = 4, 21 is a correct answer
4 Correct 1 ms 332 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 332 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 1 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 1 ms 332 KB n = 4, 21 is a correct answer
4 Correct 1 ms 332 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 332 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -