oj.uz

Submission #916844

# Submission time Handle Problem Language Result Execution time Memory
916844 2024-01-26T15:17:22 Z thangdz2k7 Bitaro's travel (JOI23_travel) C++17
0 / 100
 3000 ms 49036 KB 
#include <bits/stdc++.h>
#define ll long long


using namespace std;

const int N = 2e5 + 5;

int n, x[N];
int q;

int Max[N][20];
int Min[N][20];
int LG[N];

void prepare(){
    for (int i = n; i >= 1; -- i){
        Max[i][0] = 2 * x[i] - x[i - 1];
        Min[i][0] = 2 * x[i] - x[i + 1];
        for (int j = 1; j < 20; ++ j){
            int u = i + (1 << (j - 1));
            if (u > n) break;
            Max[i][j] = max(Max[i][j - 1], Max[u][j - 1]);
            Min[i][j] = min(Min[i][j - 1], Min[u][j - 1]);
        }
        LG[i] = log2(i);
    }
}

int getmax(int l, int r){
    int lg = LG[r - l + 1];
    return max(Max[l][lg], Max[r - (1 << lg) + 1][lg]);
}

int getmin(int l, int r){
    int lg = LG[r - l + 1];
    return min(Min[l][lg], Min[r - (1 << lg) + 1][lg]);
}

ll calc(int l, int p, int r){
    if (l == 0) return x[n] - p;
    if (r == n + 1) return p - x[1];

    //2 * x - x-1 > r - x

    if (p - x[l] <= x[r] - p){
        // 2 * x[k] - x[k - 1] > x[r];

        int L = 2;
        int R = l - 1;
        int ans = 1;
        while (L <= R){
            int mid = L + R >> 1;
            if (getmax(mid, l - 1) > x[r]){
                ans = mid;
                L = mid + 1;

            }
            else R = mid - 1;
        }

        ans = l;

        return calc(ans - 1, x[ans], r) + p - x[ans];
    }

    // 2 * x[k] - x[k + 1] <= x[l]

    int L = r + 1;
    int R = n - 1;
    int ans = n;
    while (L <= R){
        int mid = L + R >> 1;
        if (getmin(r + 1, mid) <= x[l]){
            R = mid - 1;
            ans = mid;
        }
        else L = mid + 1;
    }

    //ans = r;

    return calc(l, x[ans], ans + 1) + x[ans] - p;
}

void solve(){
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> x[i];
    prepare();

    cin >> q;
    while (q --){
        int k; cin >> k;
        int r = lower_bound(x + 1, x + n + 1, k) - x;
        int l = r - 1;
        if (x[r] == k) ++ r;
        cout << calc(l, k, r) << '\n';
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();

    return 0;
}

Compilation message

travel.cpp: In function 'long long int calc(int, int, int)':
travel.cpp:53:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |             int mid = L + R >> 1;
      |                       ~~^~~
travel.cpp:73:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |         int mid = L + R >> 1;
      |                   ~~^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 6504 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6628 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Incorrect 2 ms 4444 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 6504 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6628 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Incorrect 2 ms 4444 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Execution timed out 3065 ms 49036 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 6504 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6628 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Incorrect 2 ms 4444 KB Output isn't correct
14 Halted 0 ms 0 KB -