oj.uz

Submission #945594

# Submission time Handle Problem Language Result Execution time Memory
945594 2024-03-14T05:25:56 Z phoenix0423 Bitaro's travel (JOI23_travel) C++17
0 / 100
 468 ms 77908 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0);
#pragma GCC optimize("Ofast","unroll-loops")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int maxn = 3e5 + 5;
const int INF = 1e9 + 7;
int mn[maxn][20], mx[maxn][20];

signed main(void){
    // fastio;
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin>>a[i];
    vector<int> b(n), c(n);
    for(int i = 0; i < n; i++){
        if(i == n - 1) mx[i][0] = INF;
        else mx[i][0] = 2 * a[i + 1] - a[i];
        if(!i) mn[i][0] = -INF;
        else mn[i][0] = 2 * a[i] - a[i - 1];
    }
    for(int i = 1; (1 << i) < n; i++){
        for(int j = 0; j + (1 << i) - 1 < n; j++){
            mx[j][i] = max(mx[j][i - 1], mx[j + (1 << (i - 1))][i - 1]);
            mn[j][i] = min(mn[j][i - 1], mn[j + (1 << (i - 1))][i - 1]);
        }
    }
    int q;
    cin>>q;
    auto get_max = [&](int l, int r) -> int{
        int len = __lg(r - l + 1);
        return max(mx[l][len], mx[r - (1 << len) + 1][len]);
    };
    auto get_min = [&](int l, int r) -> int{
        int len = __lg(r - l + 1);
        return min(mn[l][len], mn[r - (1 << len) + 1][len]);
    };
    auto find_first_grt = [&](int l, int r, int tar) -> int{
        if(mx[r][0] > tar) return r;
        l--;
        while(l + 1 < r){
            int m = (l + r) / 2;
            if(get_max(m, r) > tar) l = m;
            else r = m;
        }
        return l;
    };
    auto find_first_sm = [&](int l, int r, int tar) -> int{
        if(mn[l][0] <= tar) return l;
        r++;
        while(l + 1 < r){
            int m = (l + r) / 2;
            if(get_min(l, m) <= tar) r = m;
            else l = m;
        }
        return r;
    };
    while(q--){
        int x;
        cin>>x;
        int stp = lower_bound(a.begin(), a.end(), x) - a.begin();
        if(stp == n) stp--;
        if(stp != 0 && x - a[stp - 1] <= a[stp] - x) stp--;
        int l = stp, r = stp, ans = abs(x - a[stp]);
        int d = 0;
        while(true){
            if(l == 0 || r == n - 1){
                ans += a[n - 1] - a[0];
                break;
            }
            ans += a[r] - a[l];
            if(d == 0){
                int tmp = find_first_grt(0, l - 1, a[r + 1]);
                ans += a[l] - a[tmp + 1];
                l = tmp + 1;
            }
            else{
                int tmp = find_first_sm(r + 1, n - 1, a[l - 1]);
                ans += a[tmp - 1] - a[r];
                r = tmp - 1;
            }
            d ^= 1;
        }
        cout<<ans<<"\n";
    }
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 435 ms 76744 KB Output is correct
8 Correct 431 ms 76884 KB Output is correct
9 Correct 468 ms 76920 KB Output is correct
10 Correct 438 ms 76820 KB Output is correct
11 Correct 427 ms 76736 KB Output is correct
12 Correct 432 ms 77040 KB Output is correct
13 Correct 302 ms 6228 KB Output is correct
14 Correct 275 ms 3792 KB Output is correct
15 Incorrect 446 ms 77908 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 2396 KB Output is correct
2 Correct 1 ms 4548 KB Output is correct
3 Incorrect 2 ms 4700 KB Output isn't correct
4 Halted 0 ms 0 KB -