oj.uz

Submission #417159

# Submission time Handle Problem Language Result Execution time Memory
417159 2021-06-03T12:23:14 Z yuto1115 Shortcut (IOI16_shortcut) C++17
0 / 100
 1 ms 292 KB 
#include "shortcut.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++)
#define rrep(i, n) for(ll i = ll(n)-1; i >= 0; i--)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const int inf = 1001001001;
const ll linf = 1001001001001001001;

class segtree {
    int n;
    vl v;
public:
    segtree(int _n) {
        n = 1;
        while (n < _n) n *= 2;
        v.assign(2 * n, linf);
    }
    
    void update(int x, ll val) {
        assert(0 <= x and x < n);
        x += n;
        chmin(v[x], val);
        x >>= 1;
        while (x >= 1) {
            v[x] = min(v[2 * x], v[2 * x + 1]);
            x >>= 1;
        }
    }
    
    ll prod(int l, int r) {
        assert(0 <= l and l <= r and r <= n);
        l += n, r += n;
        ll res = linf;
        while (l < r) {
            if (l & 1) chmin(res, v[l++]);
            if (r & 1) chmin(res, v[--r]);
            l >>= 1, r >>= 1;
        }
        return res;
    }
};

ll find_shortcut(int n, vi l, vi d, int c) {
    vl L(n);
    rep(i, n - 1) L[i + 1] = L[i] + l[i];
    ll ok = linf, ng = 0;
    vl zip;
    rep(i, n) zip.pb(L[i] + d[i]);
    sort(all(zip));
    zip.erase(unique(all(zip)), zip.end());
    int sz = zip.size();
    vi pos(n);
    rep(i, n) pos[i] = lower_bound(all(zip), L[i] + d[i]) - zip.begin();
    auto f = [&](ll x) -> bool {
        ll p = -linf, q = linf, r = -linf, s = linf;
        segtree st(sz);
        int mx_pos = -1;
        rrep(a, n) {
            int ub = upper_bound(all(zip), x + L[a] - d[a]) - zip.begin();;
            if (mx_pos < ub) {
                st.update(pos[a], L[a] - d[a]);
                chmax(mx_pos, pos[a]);
                continue;
            }
            chmax(p, L[a] + d[a] + c - x + zip[mx_pos]);
            chmin(q, L[a] - d[a] - c + x + st.prod(ub, sz));
            chmax(r, -L[a] + d[a] + c - x + zip[mx_pos]);
            chmin(s, -L[a] - d[a] - c + x + st.prod(ub, sz));
        }
        rep(i, n - 1) {
            ll mn = max(p - L[i], r + L[i]);
            ll mx = min(q - L[i], s + L[i]);
            auto it = lower_bound(L.begin() + i + 1, L.end(), mn);
            if (it == L.end()) continue;
            if (*it > mx) continue;
            return true;
        }
        return false;
    };
    while (ok - ng > 1) {
        ll mid = (ok + ng) / 2;
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}

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 0 ms 292 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 0 ms 204 KB n = 3, 4 is a correct answer
5 Correct 0 ms 204 KB n = 2, 62 is a correct answer
6 Correct 1 ms 204 KB n = 2, 3 is a correct answer
7 Incorrect 1 ms 204 KB n = 3, incorrect answer: jury 29 vs contestant 20
8 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 0 ms 292 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 0 ms 204 KB n = 3, 4 is a correct answer
5 Correct 0 ms 204 KB n = 2, 62 is a correct answer
6 Correct 1 ms 204 KB n = 2, 3 is a correct answer
7 Incorrect 1 ms 204 KB n = 3, incorrect answer: jury 29 vs contestant 20
8 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 0 ms 292 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 0 ms 204 KB n = 3, 4 is a correct answer
5 Correct 0 ms 204 KB n = 2, 62 is a correct answer
6 Correct 1 ms 204 KB n = 2, 3 is a correct answer
7 Incorrect 1 ms 204 KB n = 3, incorrect answer: jury 29 vs contestant 20
8 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 0 ms 292 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 0 ms 204 KB n = 3, 4 is a correct answer
5 Correct 0 ms 204 KB n = 2, 62 is a correct answer
6 Correct 1 ms 204 KB n = 2, 3 is a correct answer
7 Incorrect 1 ms 204 KB n = 3, incorrect answer: jury 29 vs contestant 20
8 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 0 ms 292 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 0 ms 204 KB n = 3, 4 is a correct answer
5 Correct 0 ms 204 KB n = 2, 62 is a correct answer
6 Correct 1 ms 204 KB n = 2, 3 is a correct answer
7 Incorrect 1 ms 204 KB n = 3, incorrect answer: jury 29 vs contestant 20
8 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 0 ms 292 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 0 ms 204 KB n = 3, 4 is a correct answer
5 Correct 0 ms 204 KB n = 2, 62 is a correct answer
6 Correct 1 ms 204 KB n = 2, 3 is a correct answer
7 Incorrect 1 ms 204 KB n = 3, incorrect answer: jury 29 vs contestant 20
8 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 0 ms 292 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 0 ms 204 KB n = 3, 4 is a correct answer
5 Correct 0 ms 204 KB n = 2, 62 is a correct answer
6 Correct 1 ms 204 KB n = 2, 3 is a correct answer
7 Incorrect 1 ms 204 KB n = 3, incorrect answer: jury 29 vs contestant 20
8 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 0 ms 292 KB n = 9, 110 is a correct answer
3 Correct 1 ms 204 KB n = 4, 21 is a correct answer
4 Correct 0 ms 204 KB n = 3, 4 is a correct answer
5 Correct 0 ms 204 KB n = 2, 62 is a correct answer
6 Correct 1 ms 204 KB n = 2, 3 is a correct answer
7 Incorrect 1 ms 204 KB n = 3, incorrect answer: jury 29 vs contestant 20
8 Halted 0 ms 0 KB -