oj.uz

Submission #741530

# Submission time Handle Problem Language Result Execution time Memory
741530 2023-05-14T09:58:21 Z stevancv Bitaro's travel (JOI23_travel) C++14
5 / 100
 136 ms 31768 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 2e5 + 2;
const ll linf = 1e18;
int l[N][18], r[N][18], logs[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) l[i][0] = 2 * a[i] - a[i - 1];
    for (int j = 1; j < 18; j++) {
        for (int i = 1; i < n - (1 << j) + 1; i++) {
            l[i][j] = max(l[i][j - 1], l[i + (1 << (j - 1))][j - 1]);
        }
    }
    for (int i = 0; i < n - 1; i++) r[i][0] = 2 * a[i] - a[i + 1];
    for (int j = 1; j < 18; j++) {
        for (int i = 0; i < n - (1 << j); i++) {
            r[i][j] = min(r[i][j - 1], r[i + (1 << (j - 1))][j - 1]);
        }
    }
    int zz = 0;
    for (int i = 1; i <= n; i++) {
        if ((1 << (zz + 1)) == i) zz += 1;
        logs[i] = zz;
    }
    auto GetLeft = [&] (int p, int q) {
        if (p >= q) return 0;
        int o = logs[q - p + 1];
        return max(l[p][o], l[q - (1 << o) + 1][o]);
    };
    auto GetRight = [&] (int p, int q) {
        if (p >= q) return 0;
        int o = logs[q - p + 1];
        return min(r[p][o], r[q - (1 << o) + 1][o]);
    };
    int q; cin >> q;
    while (q--) {
        int s; cin >> s;
        if (s >= a[n - 1]) {
            cout << s - a[0] << en;
            continue;
        }
        if (s <= a[0]) {
            cout << a[n - 1] - s << en;
            continue;
        }
        int up = (int)(upper_bound(a.begin(), a.end(), s) - a.begin());
        int lo = up - 1;
        if (a[lo] == s) lo -= 1;
        int uu = 0;
        ll ans = s;
        if (s - a[lo] > a[up] - s) {
            uu = 1;
            ans = -s;
        }
        while (1) {
            if (uu == 0) {
                if (GetLeft(1, lo) <= a[up] || lo <= 0) {
                    ans += a[n - 1] - 2 * a[0];
                    cout << ans << en;
                    break;
                }
                int lef = 1, rig = lo, gde = -1;
                while (lef <= rig) {
                    int mid = lef + rig >> 1;
                    if (GetLeft(mid, lo) > a[up]) {
                        lef = mid + 1;
                        gde = mid;
                    }
                    else rig = mid - 1;
                }
                assert(gde != -1);
                ans -= 2 * a[gde];
                uu ^= 1;
                lo = gde - 1;
                up += 1;
                continue;
            }
            if (GetRight(up, n - 2) > a[lo] || up >= n - 1) {
                ans += 2 * a[n - 1] - a[0];
                cout << ans << en;
                break;
            }
            int lef = up, rig = n - 2, gde = -1;
            while (lef <= rig) {
                int mid = lef + rig >> 1;
                if (GetRight(up, mid) <= a[lo]) {
                    rig = mid - 1;
                    gde = mid;
                }
                else lef = mid + 1;
            }
            assert(gde != -1);
            ans += 2 * a[gde];
            uu ^= 1;
            up = gde + 1;
            lo -= 1;
        }
    }
    return 0;
}

Compilation message

travel.cpp: In function 'int main()':
travel.cpp:75:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |                     int mid = lef + rig >> 1;
      |                               ~~~~^~~~~
travel.cpp:96:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |                 int mid = lef + rig >> 1;
      |                           ~~~~^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 78 ms 31240 KB Output is correct
18 Correct 70 ms 31472 KB Output is correct
19 Correct 69 ms 31596 KB Output is correct
20 Correct 70 ms 31544 KB Output is correct
21 Correct 71 ms 31584 KB Output is correct
22 Incorrect 69 ms 31476 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 136 ms 31768 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 78 ms 31240 KB Output is correct
18 Correct 70 ms 31472 KB Output is correct
19 Correct 69 ms 31596 KB Output is correct
20 Correct 70 ms 31544 KB Output is correct
21 Correct 71 ms 31584 KB Output is correct
22 Incorrect 69 ms 31476 KB Output isn't correct
23 Halted 0 ms 0 KB -