oj.uz

Submission #559586

# Submission time Handle Problem Language Result Execution time Memory
559586 2022-05-10T08:42:11 Z elazarkoren Shortcut (IOI16_shortcut) C++17
0 / 100
 1 ms 308 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<int, int> pii;
typedef vector<pii> vii;

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

struct SegMin {
    vi seg;
    int n;
    SegMin() {}
    SegMin(int m) {
        for (n = 1; n < m; n <<= 1);
        seg.resize(2 * n, infinity);
    }
    void update(int i, ll x) {
        for (i += n; i; i >>= 1) chkmin(seg[i], x);
    }
    ll query(int l, int r) {
        ll ans = infinity;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) chkmin(ans, seg[l++]);
            if (r & 1) chkmin(ans, seg[--r]);
        }
        return ans;
    }
};

struct SegMax {
    vi seg;
    int n;
    SegMax() {}
    SegMax(int m) {
        for (n = 1; n < m; n <<= 1);
        seg.resize(2 * n);
    }
    void update(int i, ll x) {
        for (i += n; i; i >>= 1) chkmax(seg[i], x);
    }
    ll query(int l, int r) {
        ll ans = 0;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) chkmax(ans, seg[l++]);
            if (r & 1) chkmax(ans, seg[--r]);
        }
        return ans;
    }
};

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

vi vals;
inline int Val(ll y) {
    return lower_bound(all(vals), y) - vals.begin();
}
inline int Next(ll y) {
    return upper_bound(all(vals), y) - vals.begin();
}

//SegMin min_plus;
SegMin min_minus;
SegMax max_plus;
//SegMax max_minus;
int sz;

int 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;
    for (int j = 1; j < n; j++) {
        int ind = Next(k - x[j] - d[j]);
        //ll min_p = min_plus.query(ind, sz);
        ll min_m = min_minus.query(ind, sz);
        ll max_p = max_plus.query(ind, sz);
        //ll max_m = max_minus.query(ind, sz);

        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));
    }
    for (int i = 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);
        auto it = lower_bound(x, x + i, lower_y);
        if (it != x + i && *it <= 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];
    for (int i = 0; i < n; i++) {
        vals.push_back(d[i] - x[i]);
    }
    sort(all(vals));
    vals.erase(unique(all(vals)), vals.end());
    sz = vals.size();
    //min_plus = SegMin(sz);
    min_minus = SegMin(sz);
    max_plus = SegMax(sz);
    //max_minus = SegMax(sz);
    for (int i = 0; i < n; i++) {
        int ind = Val(d[i] - x[i]);
        //min_plus.update(ind, x[i] + d[i]);
        min_minus.update(ind, x[i] - d[i]);
        max_plus.update(ind, x[i] + d[i]);
        //max_minus.update(ind, x[i] - d[i]);
    }
    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 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 308 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Correct 1 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Incorrect 1 ms 212 KB n = 3, incorrect answer: jury 29 vs contestant 38
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 308 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Correct 1 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Incorrect 1 ms 212 KB n = 3, incorrect answer: jury 29 vs contestant 38
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 308 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Correct 1 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Incorrect 1 ms 212 KB n = 3, incorrect answer: jury 29 vs contestant 38
8 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 308 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Correct 1 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Incorrect 1 ms 212 KB n = 3, incorrect answer: jury 29 vs contestant 38
8 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 308 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Correct 1 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Incorrect 1 ms 212 KB n = 3, incorrect answer: jury 29 vs contestant 38
8 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 308 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Correct 1 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Incorrect 1 ms 212 KB n = 3, incorrect answer: jury 29 vs contestant 38
8 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 308 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Correct 1 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Incorrect 1 ms 212 KB n = 3, incorrect answer: jury 29 vs contestant 38
8 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 308 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Correct 1 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Incorrect 1 ms 212 KB n = 3, incorrect answer: jury 29 vs contestant 38
8 Halted 0 ms 0 KB -