oj.uz

Submission #741535

# Submission time Handle Problem Language Result Execution time Memory
741535 2023-05-14T10:08:55 Z stevancv Bitaro's travel (JOI23_travel) C++14
5 / 100
 160 ms 33608 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 596 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 2 ms 596 KB Output is correct
8 Correct 1 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 2 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 596 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 2 ms 596 KB Output is correct
8 Correct 1 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 2 ms 596 KB Output is correct
17 Correct 68 ms 30172 KB Output is correct
18 Correct 74 ms 30184 KB Output is correct
19 Correct 72 ms 30156 KB Output is correct
20 Correct 72 ms 30284 KB Output is correct
21 Correct 72 ms 30196 KB Output is correct
22 Correct 75 ms 30320 KB Output is correct
23 Correct 76 ms 31232 KB Output is correct
24 Correct 73 ms 31348 KB Output is correct
25 Incorrect 76 ms 31688 KB Output isn't correct
26 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 340 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 157 ms 31820 KB Output is correct
8 Correct 146 ms 33216 KB Output is correct
9 Correct 141 ms 33236 KB Output is correct
10 Correct 156 ms 33156 KB Output is correct
11 Correct 155 ms 33232 KB Output is correct
12 Correct 147 ms 33224 KB Output is correct
13 Correct 41 ms 3916 KB Output is correct
14 Correct 26 ms 1376 KB Output is correct
15 Incorrect 160 ms 33608 KB Output isn't correct
16 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 596 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 2 ms 596 KB Output is correct
8 Correct 1 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 2 ms 596 KB Output is correct
17 Correct 68 ms 30172 KB Output is correct
18 Correct 74 ms 30184 KB Output is correct
19 Correct 72 ms 30156 KB Output is correct
20 Correct 72 ms 30284 KB Output is correct
21 Correct 72 ms 30196 KB Output is correct
22 Correct 75 ms 30320 KB Output is correct
23 Correct 76 ms 31232 KB Output is correct
24 Correct 73 ms 31348 KB Output is correct
25 Incorrect 76 ms 31688 KB Output isn't correct
26 Halted 0 ms 0 KB -