oj.uz

Submission #423781

# Submission time Handle Problem Language Result Execution time Memory
423781 2021-06-11T12:41:19 Z jtnydv25 Shortcut (IOI16_shortcut) C++17
0 / 100
 10 ms 16716 KB 
#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
 
#ifdef LOCAL
#include <print.h>
#else
#define trace(...)
#define endl '\n'
#endif
const int N = 1 << 20;
const ll INF = 1e18;
struct Data{
    ll a, b;
    Data() : a(-INF), b(INF){}
    Data(ll a, ll b) : a(a), b(b){}
};
 
inline void merge(Data & X, const Data & Y){
    X.a = max(X.a, Y.a);
    X.b = min(X.b,Y.b);
}
 
Data prefix[N];
ll p[N];

int perm1[N], perm2[N], where[N], position[N];
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c){
    for(int i = 1; i < n; i++) p[i] = p[i - 1] + l[i - 1];
    iota(perm1, perm1 + n, 0);
    iota(perm2, perm2 + n, 0);
    sort(perm1, perm1 + n, [&](int i, int j){return d[i] - p[i] > d[j] - p[j];});
    sort(perm2, perm2 + n, [&](int i, int j){return d[i] + p[i] < d[j] + p[j];});
 
    for(int i = 0; i < n; i++) where[perm1[i]] = i;
    int mx = 0, mx2 = 0, ind_mx = 0;
    for(int i = 1; i <= n; i++){
        int ind = perm1[i - 1];
        prefix[i] = prefix[i - 1];
        merge(prefix[i], Data(p[ind] + d[ind], p[ind] - d[ind]));
        if(d[ind] > mx){
            mx2 = mx;
            mx = d[ind];
            ind_mx = ind;
        } else if(d[ind] > mx2) mx2 = d[ind];
    }
    ll lo = mx + mx2, hi = 1000000000LL * 10000000LL;
    while(lo < hi){
        ll D = (lo + hi) / 2;
        Data d1, d2;
        int cur = 0; // < 0
        for(int ind = 0; ind < n; ind++){
            int i = perm2[ind];
            while(cur < n && d[perm1[cur]] + d[i] + p[i] - p[perm1[cur]] > D) cur++;
            position[i] = cur;
        }
        
        for(int j = 0; j < n; j++){
            Data temp = prefix[position[j]];
            if(j == ind_mx){
                temp = Data();
                int k = position[j];
                for(int r = 0; r < k; r++){
                    if(perm1[r] == j) continue;
                    merge(temp, Data(p[r] + d[r], p[r] - d[r]));
                }
            }
            d1.a = max(d1.a, temp.a + d[j] + c - p[j] - D);
            d1.b = min(d1.b, temp.b - d[j] - c - p[j] + D);
            d2.a = max(d2.a, temp.a + p[j] - D + d[j] + c);
            d2.b = min(d2.b, temp.b + p[j] + D - d[j] - c);
        }
        ll L1 = d1.a, R1 = d1.b;
        ll L2 = d2.a, R2 = d2.b;
        if(L1 > R1 || L2 > R2){
            lo = D + 1;
            continue;
        } 
        bool ok = false;
        int ptr1 = 0; // first >= p[v] + L1
        int ptr2 = n; // first >= L2 - p[v];
        for(int v = 1; v < n; v++){
            ll R = min(p[v] + R1, R2 - p[v]);
            while(ptr1 < n && p[ptr1] < L1 + p[v]) ptr1++;
            while(ptr2 > 0 && p[ptr2 - 1] >= L2 - p[v]) ptr2--;
            int u = max(ptr1, ptr2);
 
            if(u >= v) continue;
            if(p[u] > R) continue;
            ok = true;
            break;
        }
        if(ok) hi = D;
        else lo = D + 1;
    }
    return lo;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16716 KB n = 4, 80 is a correct answer
2 Correct 8 ms 16716 KB n = 9, 110 is a correct answer
3 Correct 9 ms 16716 KB n = 4, 21 is a correct answer
4 Correct 9 ms 16716 KB n = 3, 4 is a correct answer
5 Correct 9 ms 16716 KB n = 2, 62 is a correct answer
6 Correct 10 ms 16708 KB n = 2, 3 is a correct answer
7 Correct 9 ms 16712 KB n = 3, 29 is a correct answer
8 Correct 9 ms 16668 KB n = 2, 3 is a correct answer
9 Correct 10 ms 16716 KB n = 2, 3 is a correct answer
10 Correct 8 ms 16716 KB n = 2, 2000000001 is a correct answer
11 Correct 9 ms 16716 KB n = 2, 3000000000 is a correct answer
12 Correct 8 ms 16680 KB n = 3, 3000000000 is a correct answer
13 Correct 9 ms 16716 KB n = 3, 3000000000 is a correct answer
14 Correct 8 ms 16716 KB n = 4, 3000000001 is a correct answer
15 Correct 10 ms 16716 KB n = 4, 4000000000 is a correct answer
16 Correct 8 ms 16640 KB n = 5, 4000000000 is a correct answer
17 Incorrect 10 ms 16716 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000311
18 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16716 KB n = 4, 80 is a correct answer
2 Correct 8 ms 16716 KB n = 9, 110 is a correct answer
3 Correct 9 ms 16716 KB n = 4, 21 is a correct answer
4 Correct 9 ms 16716 KB n = 3, 4 is a correct answer
5 Correct 9 ms 16716 KB n = 2, 62 is a correct answer
6 Correct 10 ms 16708 KB n = 2, 3 is a correct answer
7 Correct 9 ms 16712 KB n = 3, 29 is a correct answer
8 Correct 9 ms 16668 KB n = 2, 3 is a correct answer
9 Correct 10 ms 16716 KB n = 2, 3 is a correct answer
10 Correct 8 ms 16716 KB n = 2, 2000000001 is a correct answer
11 Correct 9 ms 16716 KB n = 2, 3000000000 is a correct answer
12 Correct 8 ms 16680 KB n = 3, 3000000000 is a correct answer
13 Correct 9 ms 16716 KB n = 3, 3000000000 is a correct answer
14 Correct 8 ms 16716 KB n = 4, 3000000001 is a correct answer
15 Correct 10 ms 16716 KB n = 4, 4000000000 is a correct answer
16 Correct 8 ms 16640 KB n = 5, 4000000000 is a correct answer
17 Incorrect 10 ms 16716 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000311
18 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16716 KB n = 4, 80 is a correct answer
2 Correct 8 ms 16716 KB n = 9, 110 is a correct answer
3 Correct 9 ms 16716 KB n = 4, 21 is a correct answer
4 Correct 9 ms 16716 KB n = 3, 4 is a correct answer
5 Correct 9 ms 16716 KB n = 2, 62 is a correct answer
6 Correct 10 ms 16708 KB n = 2, 3 is a correct answer
7 Correct 9 ms 16712 KB n = 3, 29 is a correct answer
8 Correct 9 ms 16668 KB n = 2, 3 is a correct answer
9 Correct 10 ms 16716 KB n = 2, 3 is a correct answer
10 Correct 8 ms 16716 KB n = 2, 2000000001 is a correct answer
11 Correct 9 ms 16716 KB n = 2, 3000000000 is a correct answer
12 Correct 8 ms 16680 KB n = 3, 3000000000 is a correct answer
13 Correct 9 ms 16716 KB n = 3, 3000000000 is a correct answer
14 Correct 8 ms 16716 KB n = 4, 3000000001 is a correct answer
15 Correct 10 ms 16716 KB n = 4, 4000000000 is a correct answer
16 Correct 8 ms 16640 KB n = 5, 4000000000 is a correct answer
17 Incorrect 10 ms 16716 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000311
18 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16716 KB n = 4, 80 is a correct answer
2 Correct 8 ms 16716 KB n = 9, 110 is a correct answer
3 Correct 9 ms 16716 KB n = 4, 21 is a correct answer
4 Correct 9 ms 16716 KB n = 3, 4 is a correct answer
5 Correct 9 ms 16716 KB n = 2, 62 is a correct answer
6 Correct 10 ms 16708 KB n = 2, 3 is a correct answer
7 Correct 9 ms 16712 KB n = 3, 29 is a correct answer
8 Correct 9 ms 16668 KB n = 2, 3 is a correct answer
9 Correct 10 ms 16716 KB n = 2, 3 is a correct answer
10 Correct 8 ms 16716 KB n = 2, 2000000001 is a correct answer
11 Correct 9 ms 16716 KB n = 2, 3000000000 is a correct answer
12 Correct 8 ms 16680 KB n = 3, 3000000000 is a correct answer
13 Correct 9 ms 16716 KB n = 3, 3000000000 is a correct answer
14 Correct 8 ms 16716 KB n = 4, 3000000001 is a correct answer
15 Correct 10 ms 16716 KB n = 4, 4000000000 is a correct answer
16 Correct 8 ms 16640 KB n = 5, 4000000000 is a correct answer
17 Incorrect 10 ms 16716 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000311
18 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16716 KB n = 4, 80 is a correct answer
2 Correct 8 ms 16716 KB n = 9, 110 is a correct answer
3 Correct 9 ms 16716 KB n = 4, 21 is a correct answer
4 Correct 9 ms 16716 KB n = 3, 4 is a correct answer
5 Correct 9 ms 16716 KB n = 2, 62 is a correct answer
6 Correct 10 ms 16708 KB n = 2, 3 is a correct answer
7 Correct 9 ms 16712 KB n = 3, 29 is a correct answer
8 Correct 9 ms 16668 KB n = 2, 3 is a correct answer
9 Correct 10 ms 16716 KB n = 2, 3 is a correct answer
10 Correct 8 ms 16716 KB n = 2, 2000000001 is a correct answer
11 Correct 9 ms 16716 KB n = 2, 3000000000 is a correct answer
12 Correct 8 ms 16680 KB n = 3, 3000000000 is a correct answer
13 Correct 9 ms 16716 KB n = 3, 3000000000 is a correct answer
14 Correct 8 ms 16716 KB n = 4, 3000000001 is a correct answer
15 Correct 10 ms 16716 KB n = 4, 4000000000 is a correct answer
16 Correct 8 ms 16640 KB n = 5, 4000000000 is a correct answer
17 Incorrect 10 ms 16716 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000311
18 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16716 KB n = 4, 80 is a correct answer
2 Correct 8 ms 16716 KB n = 9, 110 is a correct answer
3 Correct 9 ms 16716 KB n = 4, 21 is a correct answer
4 Correct 9 ms 16716 KB n = 3, 4 is a correct answer
5 Correct 9 ms 16716 KB n = 2, 62 is a correct answer
6 Correct 10 ms 16708 KB n = 2, 3 is a correct answer
7 Correct 9 ms 16712 KB n = 3, 29 is a correct answer
8 Correct 9 ms 16668 KB n = 2, 3 is a correct answer
9 Correct 10 ms 16716 KB n = 2, 3 is a correct answer
10 Correct 8 ms 16716 KB n = 2, 2000000001 is a correct answer
11 Correct 9 ms 16716 KB n = 2, 3000000000 is a correct answer
12 Correct 8 ms 16680 KB n = 3, 3000000000 is a correct answer
13 Correct 9 ms 16716 KB n = 3, 3000000000 is a correct answer
14 Correct 8 ms 16716 KB n = 4, 3000000001 is a correct answer
15 Correct 10 ms 16716 KB n = 4, 4000000000 is a correct answer
16 Correct 8 ms 16640 KB n = 5, 4000000000 is a correct answer
17 Incorrect 10 ms 16716 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000311
18 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16716 KB n = 4, 80 is a correct answer
2 Correct 8 ms 16716 KB n = 9, 110 is a correct answer
3 Correct 9 ms 16716 KB n = 4, 21 is a correct answer
4 Correct 9 ms 16716 KB n = 3, 4 is a correct answer
5 Correct 9 ms 16716 KB n = 2, 62 is a correct answer
6 Correct 10 ms 16708 KB n = 2, 3 is a correct answer
7 Correct 9 ms 16712 KB n = 3, 29 is a correct answer
8 Correct 9 ms 16668 KB n = 2, 3 is a correct answer
9 Correct 10 ms 16716 KB n = 2, 3 is a correct answer
10 Correct 8 ms 16716 KB n = 2, 2000000001 is a correct answer
11 Correct 9 ms 16716 KB n = 2, 3000000000 is a correct answer
12 Correct 8 ms 16680 KB n = 3, 3000000000 is a correct answer
13 Correct 9 ms 16716 KB n = 3, 3000000000 is a correct answer
14 Correct 8 ms 16716 KB n = 4, 3000000001 is a correct answer
15 Correct 10 ms 16716 KB n = 4, 4000000000 is a correct answer
16 Correct 8 ms 16640 KB n = 5, 4000000000 is a correct answer
17 Incorrect 10 ms 16716 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000311
18 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16716 KB n = 4, 80 is a correct answer
2 Correct 8 ms 16716 KB n = 9, 110 is a correct answer
3 Correct 9 ms 16716 KB n = 4, 21 is a correct answer
4 Correct 9 ms 16716 KB n = 3, 4 is a correct answer
5 Correct 9 ms 16716 KB n = 2, 62 is a correct answer
6 Correct 10 ms 16708 KB n = 2, 3 is a correct answer
7 Correct 9 ms 16712 KB n = 3, 29 is a correct answer
8 Correct 9 ms 16668 KB n = 2, 3 is a correct answer
9 Correct 10 ms 16716 KB n = 2, 3 is a correct answer
10 Correct 8 ms 16716 KB n = 2, 2000000001 is a correct answer
11 Correct 9 ms 16716 KB n = 2, 3000000000 is a correct answer
12 Correct 8 ms 16680 KB n = 3, 3000000000 is a correct answer
13 Correct 9 ms 16716 KB n = 3, 3000000000 is a correct answer
14 Correct 8 ms 16716 KB n = 4, 3000000001 is a correct answer
15 Correct 10 ms 16716 KB n = 4, 4000000000 is a correct answer
16 Correct 8 ms 16640 KB n = 5, 4000000000 is a correct answer
17 Incorrect 10 ms 16716 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000311
18 Halted 0 ms 0 KB -