oj.uz

Submission #792449

# Submission time Handle Problem Language Result Execution time Memory
792449 2023-07-25T05:06:37 Z vjudge1 Bitaro's travel (JOI23_travel) C++17
0 / 100
 497 ms 39648 KB 
#include <bits/stdc++.h>

#define fi first
#define se second

const int N = 200200;

using namespace std;

int n;
long long a[N];
long long t[N][20];
long long L[N];

long long get(int l, int r)
{
    int g = L[r - l + 1];
    return max(t[l][g], t[r - (1 << g) + 1][g]);
}

long long go_one(int &l, int&r, int &k)
{
    if (l == 1 && r == n) {
        return 0;
    }
    long long res;
    if (abs(a[k] - a[l - 1]) <= abs(a[k] - a[r + 1])) {
        l--;
        res = abs(a[k] - a[l]);
        k = l;
    } else {
        r++;
        res = abs(a[k] - a[r]);
        k = r;
    }
    return res;
}

long long solve(int k)
{
    int l = k, r = k;
    long long res = go_one(l, r, k);
    while (l > 1 || r < n) {
        if (l == k) {
            int tl = 1, tr = l;
            while (tl < tr) {
                int tm = (tl + tr) / 2;
                if (get(tm, l - 1) <= a[r] - a[l]) {
                    tr = tm;
                } else {
                    tl = tm + 1;
                }
            }
            res += a[l] - a[tl];
            l = k = tl;
        } else {
            int tl = r, tr = n;
            while (tl < tr) {
                int tm = (tl + tr) / 2;
                if (get(r, tm) < a[r] - a[l]) {
                    tl = tm + 1;
                } else {
                    tr = tm;
                }
            }
            res += a[tl] - a[r];
            r = k = tl;
        }
        res += go_one(l, r, k);
    }
    return res;
}

int main()
{
    #ifdef zxc
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    a[0] = -2e9;
    a[n + 1] = 2e9;

    for (int i = 1; i <= n; i++) {
        t[i][0] = a[i + 1] - a[i];
    }
    for (int i = 2; i < N; i++) {
        L[i] = L[i / 2] + 1;
    }
    for (int i = 1; i < 20; i++) {
        for (int j = 1; j + (1 << i) - 1 <= n; j++) {
            t[j][i] = max(t[j][i - 1], t[j + (1 << i)][i - 1]);
        }
    }

    int q;
    cin >> q;
    while (q--) {
        long long x;
        cin >> x;
        int i = lower_bound(a + 1, a + n + 1, x) - a;
        if (i > 1 && abs(a[i - 1] - x) <= abs(a[i] - x)) {
            i--;
        }

        cout << solve(i) + abs(a[i] - x) << "\n";
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 2132 KB Output is correct
3 Correct 1 ms 2220 KB Output is correct
4 Correct 1 ms 2132 KB Output is correct
5 Incorrect 2 ms 2260 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 2132 KB Output is correct
3 Correct 1 ms 2220 KB Output is correct
4 Correct 1 ms 2132 KB Output is correct
5 Incorrect 2 ms 2260 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Correct 1 ms 1876 KB Output is correct
5 Correct 1 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 415 ms 38592 KB Output is correct
8 Correct 497 ms 38696 KB Output is correct
9 Correct 414 ms 38700 KB Output is correct
10 Correct 418 ms 38692 KB Output is correct
11 Correct 445 ms 38588 KB Output is correct
12 Correct 435 ms 38692 KB Output is correct
13 Correct 256 ms 5688 KB Output is correct
14 Correct 223 ms 3080 KB Output is correct
15 Incorrect 489 ms 39648 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 2132 KB Output is correct
3 Correct 1 ms 2220 KB Output is correct
4 Correct 1 ms 2132 KB Output is correct
5 Incorrect 2 ms 2260 KB Output isn't correct
6 Halted 0 ms 0 KB -