oj.uz

Submission #559629

# Submission time Handle Problem Language Result Execution time Memory
559629 2022-05-10T10:29:14 Z elazarkoren Shortcut (IOI16_shortcut) C++17
0 / 100
 2 ms 444 KB 
#include "shortcut.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
//#define int ll
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;

const int MAX_N = 1e6 + 5;
const ll infinity = 1e18;

ll x[MAX_N];
ll d[MAX_N];
ll c;

int n;

int ind1[MAX_N];
int ind2[MAX_N];

//(i < j)
//xj - xi + di + dj > k  -->
//di - xi > k - xj - dj

//di + dj + |xi - y| + |xj - z| + c <= k -->
//  (xi - di) + (xj - dj) + (k - c) >= y + z
//  (xi + di) + (xj + dj) - (k - c) <= y + z
//  (xi - di) - (xj + dj) + (k - c) >= y - z
//  (xi + di) - (xj - dj) - (k - c) <= y - z

bool Ok(ll k) {
    ll lower_plus = -infinity, lower_minus = -infinity;
    ll upper_plus = infinity, upper_minus = infinity;
    pii p1 = {-infinity, -infinity}, p2 = {infinity, infinity};
    bitset<MAX_N> visited;
    for (int j1 = 0, i = 0; j1 < n; j1++) {
        int j = ind1[j1];
        while (i < n && x[j] + d[j] - (x[ind2[i]] - d[ind2[i]]) > k) {
            ll v = x[ind2[i]] + d[ind2[i]];
            if (v >= p1.x) {
                p1.y = p1.x;
                p1.x = v;
            } else if (v > p1.y) p1.y = v;
            v = x[ind2[i]] - d[ind2[i]];
            if (v <= p2.x) {
                p2.y = p2.x;
                p2.x = v;
            } else if (v < p2.y) p2.y = v;
            visited[ind2[i]] = true;
            i++;
        }

        ll max_p = p1.x, min_m = p2.x;
        if (visited[j] && max_p == x[j] + d[j]) max_p = p1.y;
        if (visited[j] && min_m == x[j] - d[j]) min_m = p2.y;
        chkmax(lower_plus, max_p + x[j] + d[j] - (k - c));
        chkmax(lower_minus, max_p - (x[j] - d[j]) - (k - c));
        chkmin(upper_plus, min_m + (x[j] - d[j]) + (k - c));
        chkmin(upper_minus, min_m - (x[j] + d[j]) + (k - c));
    }
    int mid = n;
    ll last = infinity;
    for (int i = 0; i < n; i++) {
        ll z = x[i];
        ll lower_y = max(lower_minus + z, lower_plus - z);
        if (lower_y > last) {
            mid = i;
            break;
        }
        last = lower_y;
    }
    for (int i = 1, j = 0; i < mid; i++) {
        ll z = x[i];
        ll lower_y = max(lower_minus + z, lower_plus - z);
        ll upper_y = min(upper_minus + z, upper_plus - z);
        while (j + 1 < i && x[j + 1] <= upper_y) j++;
        if (j != i && x[j] >= lower_y) return true;
    }
    for (int i = mid, j = 0; i < n; i++) {
        ll z = x[i];
        ll lower_y = max(lower_minus + z, lower_plus - z);
        ll upper_y = min(upper_minus + z, upper_plus - z);
        while (j < i && x[j] < lower_y) j++;
        if (j != i && x[j] <= upper_y) return true;
    }
    return false;
}

ll find_shortcut(int32_t N, vector<int32_t> l, vector<int32_t> D, int32_t C) {
    n = N;
    c = C;
    for (int i = 1; i < n; i++) x[i] = x[i - 1] + l[i - 1];
    for (int i = 0; i < n; i++) d[i] = D[i], ind1[i] = ind2[i] = i;
    sort(ind1, ind1 + n, [&] (int i, int j) {
        return x[i] + d[i] < x[j] + d[j];
    });
    sort(ind2, ind2 + n, [&] (int i, int j) {
        return x[i] - d[i] < x[j] - d[j];
    });
    ll begin = 0, end = 1e18, mid;
    ll max_d = 0;
    for (int i = 0; i < n; i++) {
        chkmax(begin, max_d + d[i]);
        chkmax(max_d, ll(d[i]));
    }
    while (begin < end) {
        mid = (begin + end) >> 1;
        if (Ok(mid)) {
            end = mid;
        } else begin = mid + 1;
    }
    return end;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB n = 4, 80 is a correct answer
2 Correct 2 ms 340 KB n = 9, 110 is a correct answer
3 Correct 1 ms 436 KB n = 4, 21 is a correct answer
4 Correct 1 ms 440 KB n = 3, 4 is a correct answer
5 Correct 1 ms 340 KB n = 2, 62 is a correct answer
6 Correct 1 ms 340 KB n = 2, 3 is a correct answer
7 Correct 1 ms 436 KB n = 3, 29 is a correct answer
8 Correct 1 ms 440 KB n = 2, 3 is a correct answer
9 Correct 1 ms 436 KB n = 2, 3 is a correct answer
10 Correct 1 ms 340 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 340 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 340 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 340 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 340 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 440 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 340 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 444 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 340 KB n = 10, 3189 is a correct answer
19 Incorrect 1 ms 340 KB n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000
20 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB n = 4, 80 is a correct answer
2 Correct 2 ms 340 KB n = 9, 110 is a correct answer
3 Correct 1 ms 436 KB n = 4, 21 is a correct answer
4 Correct 1 ms 440 KB n = 3, 4 is a correct answer
5 Correct 1 ms 340 KB n = 2, 62 is a correct answer
6 Correct 1 ms 340 KB n = 2, 3 is a correct answer
7 Correct 1 ms 436 KB n = 3, 29 is a correct answer
8 Correct 1 ms 440 KB n = 2, 3 is a correct answer
9 Correct 1 ms 436 KB n = 2, 3 is a correct answer
10 Correct 1 ms 340 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 340 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 340 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 340 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 340 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 440 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 340 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 444 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 340 KB n = 10, 3189 is a correct answer
19 Incorrect 1 ms 340 KB n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000
20 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB n = 4, 80 is a correct answer
2 Correct 2 ms 340 KB n = 9, 110 is a correct answer
3 Correct 1 ms 436 KB n = 4, 21 is a correct answer
4 Correct 1 ms 440 KB n = 3, 4 is a correct answer
5 Correct 1 ms 340 KB n = 2, 62 is a correct answer
6 Correct 1 ms 340 KB n = 2, 3 is a correct answer
7 Correct 1 ms 436 KB n = 3, 29 is a correct answer
8 Correct 1 ms 440 KB n = 2, 3 is a correct answer
9 Correct 1 ms 436 KB n = 2, 3 is a correct answer
10 Correct 1 ms 340 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 340 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 340 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 340 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 340 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 440 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 340 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 444 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 340 KB n = 10, 3189 is a correct answer
19 Incorrect 1 ms 340 KB n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000
20 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB n = 4, 80 is a correct answer
2 Correct 2 ms 340 KB n = 9, 110 is a correct answer
3 Correct 1 ms 436 KB n = 4, 21 is a correct answer
4 Correct 1 ms 440 KB n = 3, 4 is a correct answer
5 Correct 1 ms 340 KB n = 2, 62 is a correct answer
6 Correct 1 ms 340 KB n = 2, 3 is a correct answer
7 Correct 1 ms 436 KB n = 3, 29 is a correct answer
8 Correct 1 ms 440 KB n = 2, 3 is a correct answer
9 Correct 1 ms 436 KB n = 2, 3 is a correct answer
10 Correct 1 ms 340 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 340 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 340 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 340 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 340 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 440 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 340 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 444 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 340 KB n = 10, 3189 is a correct answer
19 Incorrect 1 ms 340 KB n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000
20 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB n = 4, 80 is a correct answer
2 Correct 2 ms 340 KB n = 9, 110 is a correct answer
3 Correct 1 ms 436 KB n = 4, 21 is a correct answer
4 Correct 1 ms 440 KB n = 3, 4 is a correct answer
5 Correct 1 ms 340 KB n = 2, 62 is a correct answer
6 Correct 1 ms 340 KB n = 2, 3 is a correct answer
7 Correct 1 ms 436 KB n = 3, 29 is a correct answer
8 Correct 1 ms 440 KB n = 2, 3 is a correct answer
9 Correct 1 ms 436 KB n = 2, 3 is a correct answer
10 Correct 1 ms 340 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 340 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 340 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 340 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 340 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 440 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 340 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 444 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 340 KB n = 10, 3189 is a correct answer
19 Incorrect 1 ms 340 KB n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000
20 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB n = 4, 80 is a correct answer
2 Correct 2 ms 340 KB n = 9, 110 is a correct answer
3 Correct 1 ms 436 KB n = 4, 21 is a correct answer
4 Correct 1 ms 440 KB n = 3, 4 is a correct answer
5 Correct 1 ms 340 KB n = 2, 62 is a correct answer
6 Correct 1 ms 340 KB n = 2, 3 is a correct answer
7 Correct 1 ms 436 KB n = 3, 29 is a correct answer
8 Correct 1 ms 440 KB n = 2, 3 is a correct answer
9 Correct 1 ms 436 KB n = 2, 3 is a correct answer
10 Correct 1 ms 340 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 340 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 340 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 340 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 340 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 440 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 340 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 444 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 340 KB n = 10, 3189 is a correct answer
19 Incorrect 1 ms 340 KB n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000
20 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB n = 4, 80 is a correct answer
2 Correct 2 ms 340 KB n = 9, 110 is a correct answer
3 Correct 1 ms 436 KB n = 4, 21 is a correct answer
4 Correct 1 ms 440 KB n = 3, 4 is a correct answer
5 Correct 1 ms 340 KB n = 2, 62 is a correct answer
6 Correct 1 ms 340 KB n = 2, 3 is a correct answer
7 Correct 1 ms 436 KB n = 3, 29 is a correct answer
8 Correct 1 ms 440 KB n = 2, 3 is a correct answer
9 Correct 1 ms 436 KB n = 2, 3 is a correct answer
10 Correct 1 ms 340 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 340 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 340 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 340 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 340 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 440 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 340 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 444 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 340 KB n = 10, 3189 is a correct answer
19 Incorrect 1 ms 340 KB n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000
20 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB n = 4, 80 is a correct answer
2 Correct 2 ms 340 KB n = 9, 110 is a correct answer
3 Correct 1 ms 436 KB n = 4, 21 is a correct answer
4 Correct 1 ms 440 KB n = 3, 4 is a correct answer
5 Correct 1 ms 340 KB n = 2, 62 is a correct answer
6 Correct 1 ms 340 KB n = 2, 3 is a correct answer
7 Correct 1 ms 436 KB n = 3, 29 is a correct answer
8 Correct 1 ms 440 KB n = 2, 3 is a correct answer
9 Correct 1 ms 436 KB n = 2, 3 is a correct answer
10 Correct 1 ms 340 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 340 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 340 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 340 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 340 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 440 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 340 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 444 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 340 KB n = 10, 3189 is a correct answer
19 Incorrect 1 ms 340 KB n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000
20 Halted 0 ms 0 KB -