oj.uz

Submission #871104

# Submission time Handle Problem Language Result Execution time Memory
871104 2023-11-09T22:28:19 Z Pekiban Bitaro's travel (JOI23_travel) C++17
0 / 100
 10 ms 31648 KB 
#include <bits/stdc++.h>
    
using namespace std;
    
const int mxN = 2e5+2, LOG = 20;
int mx[LOG][mxN], mn[LOG][mxN], lg[mxN];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    lg[1] = 0;
    for (int i = 2; i < mxN; ++i) {
        lg[i] = lg[i/2]+1;
    }
    int n;
    cin >> n;
    vector<int> a(n+2);
    a[0] = -1, a[n+1] = 2e9;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; ++i) {
        if (i != 1) mx[0][i] = 2*a[i] - a[i-1];
        if (i != n) mn[0][i] = 2*a[i] - a[i+1];
    }
    for (int i = 1; i < LOG; ++i) {
        for (int j = 1; j + (1 << i) - 1 < mxN; ++j) {
            if (j != 1) mx[i][j] = max(mx[i-1][j], mx[i-1][j + (1 << (i - 1))]);
            if (j != n) mn[i][j] = min(mn[i-1][j], mn[i-1][j + (1 << (i - 1))]);
        }
    }
    auto mnq = [&](int l, int r) {return min(mn[lg[r-l+1]][l], mn[lg[r-l+1]][r-(1 << lg[r-l+1]) + 1]);};
    auto mxq = [&](int l, int r) {return max(mx[lg[r-l+1]][l], mx[lg[r-l+1]][r-(1 << lg[r-l+1]) + 1]);};
    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        int b = lower_bound(a.begin(), a.end(), x) - a.begin();
        if (b == n+1) {
            b = n;
        }
        else if (b == 0) {
            b = 1;
        }
        else {
            if (x - a[b-1] <= a[b] - x) b--;
        }
        long long ans = abs(x-a[b]) + a[n] - a[1]; // verovatno staje u int
        int l = b, r = b; // dir = 1 => idi desno, dir = 0 => idi levo.
        bool dir = (b == 1 ? 1 : (b == n ? 0 : (a[b] - a[b-1] <= a[b+1] - a[b] ? 0 : 1)));
        while (l != 1 && r != n) {
            if (dir) {
                if (r == n-1 || mnq(r+1, n-1) > a[l-1]) {
                    ans += a[n] - a[l];
                    break;
                }
                int le = r+1, ri = n-1, t = 0;
                while (le <= ri) {
                    int mid = (le + ri)/2;
                    if (mnq(r+1, mid) <= a[l-1]) {
                        t = mid;
                        ri = mid-1;
                    }
                    else {
                        le = mid+1;
                    }
                }
                ans += a[t] - a[l];
                r = t;
            }
            else {
                if (l == 2 || mxq(2, l-1) <= a[r+1]) {
                    ans += a[r] - a[1];
                    break;
                }
                int le = 2, ri = l-1, t = 0;
                while (le <= ri) {
                    int mid = (le + ri)/2;
                    if (mxq(mid, l-1) > a[r+1]) {
                        t = mid;
                        le = mid+1;
                    }
                    else {
                        ri = mid-1;
                    }
                }
                ans += a[r] - a[t];
                l = t;
            }
            dir ^= 1;
        }
        cout << ans << '\n';
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 31320 KB Output is correct
2 Correct 10 ms 31320 KB Output is correct
3 Correct 8 ms 31324 KB Output is correct
4 Correct 9 ms 31648 KB Output is correct
5 Correct 8 ms 31420 KB Output is correct
6 Correct 8 ms 31324 KB Output is correct
7 Correct 8 ms 31324 KB Output is correct
8 Incorrect 8 ms 29348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 31320 KB Output is correct
2 Correct 10 ms 31320 KB Output is correct
3 Correct 8 ms 31324 KB Output is correct
4 Correct 9 ms 31648 KB Output is correct
5 Correct 8 ms 31420 KB Output is correct
6 Correct 8 ms 31324 KB Output is correct
7 Correct 8 ms 31324 KB Output is correct
8 Incorrect 8 ms 29348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31324 KB Output is correct
2 Correct 8 ms 31324 KB Output is correct
3 Incorrect 8 ms 29276 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 31320 KB Output is correct
2 Correct 10 ms 31320 KB Output is correct
3 Correct 8 ms 31324 KB Output is correct
4 Correct 9 ms 31648 KB Output is correct
5 Correct 8 ms 31420 KB Output is correct
6 Correct 8 ms 31324 KB Output is correct
7 Correct 8 ms 31324 KB Output is correct
8 Incorrect 8 ms 29348 KB Output isn't correct
9 Halted 0 ms 0 KB -