oj.uz

Submission #792512

# Submission time Handle Problem Language Result Execution time Memory
792512 2023-07-25T06:13:17 Z vjudge1 Bitaro's travel (JOI23_travel) C++17
100 / 100
 766 ms 61932 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const ll INF = 1e18;
const int N = 2e5 + 10;

template<typename T>
struct SparseTable {
    int len;
    vector<vector<T>> st;
    T (*F) (T, T);
    void init(vector<T> &a, T (*f)(T, T)) {
        len = (int)a.size();
        F = f;
        int mxpw = 32 - __builtin_clz(len);
        st.resize(mxpw);
        st[0] = a;  
        for(int k = 1; k < mxpw; k++) {
            st[k].resize(len - (1 << k) + 1);
            for(int i = 0; i < (int)st[k].size(); i++) 
                st[k][i] = F(st[k - 1][i], st[k - 1][i + (1 << k - 1)]);
        }
    }
    T get(int l, int r) {
        assert(l >= 0 && r < len);
        int mxpw = 31 - __builtin_clz(r - l + 1);
        return F(st[mxpw][l], st[mxpw][r - (1 << mxpw) + 1]);
    }
};

SparseTable<ll> st_ld, st_rd;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin >> n;
    vector<ll> x(n + 2);
    x[0] = -INF; x[n + 1] = INF;

    for(int i = 1; i <= n; i++)
        cin >> x[i];
    vector<ll> b(n + 1);
    for(int i = 1; i <= n; i++) 
        b[i] = 2 * x[i + 1] - x[i];
    st_ld.init(b, [](ll a, ll b) {return (a > b ? a : b);});
    for(int i = 1; i <= n; i++) {
        b[i] = x[i] - 2 * x[i - 1];
    }
    st_rd.init(b, [](ll x, ll y) {return (x > y ? x : y);});
    int q;
    cin >> q;
    while(q --> 0) {
        int st;
        cin >> st;
        if(st <= x[1]) {
            cout << x[n] - st << '\n';
            continue;
        }
        if(st >= x[n]) {
            cout << st - x[1] << '\n';
            continue;
        }
        int lb, rb, bin_lb, bin_rb;
        bool turn = 0;
        bin_lb = 0, bin_rb = n + 1;
        while(bin_rb - bin_lb > 1) {
            int mid = (bin_rb + bin_lb) / 2;
            if(x[mid] < st) bin_lb = mid;
            else bin_rb = mid;
        }
        lb = bin_lb;
        bin_lb = 0, bin_rb = n + 1;
        while(bin_rb - bin_lb > 1) {
            int mid = (bin_rb + bin_lb) / 2;
            if(x[mid] > st) bin_rb = mid;
            else bin_lb = mid;
        }
        ll sum = 0;
        rb = bin_rb;
        sum += min(st - x[lb], x[rb] - st);
        if(st - x[lb] <= x[rb] - st) rb--;
        else lb++, turn = 1;
        // cout << lb << ' ' << rb << ' ' << sum << ' ' << turn << '\n';
        while(lb > 1 || rb < n) {
            if(!turn) {
                bin_lb = 0, bin_rb = lb;
                while(bin_rb - bin_lb > 1) {
                    int mid = (bin_lb + bin_rb) / 2;
                    if(st_ld.get(mid, lb - 1) <= x[rb + 1]) bin_rb = mid;
                    else bin_lb = mid;
                }
                sum += x[lb] - x[bin_rb];
                lb = bin_rb;
                if(rb < n) sum += x[++rb] - x[lb];
            } else {
                bin_lb = rb; bin_rb = n + 1;
                while(bin_rb - bin_lb > 1) {
                    int mid = (bin_rb + bin_lb) / 2;
                    if(st_rd.get(rb + 1, mid) < -x[lb - 1]) bin_lb = mid;
                    else bin_rb = mid;
                }
                sum += x[bin_lb] - x[rb];
                rb = bin_lb;
                if(lb > 1) sum += x[rb] - x[--lb];
            }
            // cout << lb << ' ' << rb << ' ' << sum << ' ' << turn << '\n';
            turn = !turn;
        }
        cout << sum << '\n';
    }
}

Compilation message

travel.cpp: In instantiation of 'void SparseTable<T>::init(std::vector<_Tp>&, T (*)(T, T)) [with T = long long int]':
travel.cpp:48:59:   required from here
travel.cpp:23:66: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   23 |                 st[k][i] = F(st[k - 1][i], st[k - 1][i + (1 << k - 1)]);
      |                                                                ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 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 1 ms 596 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 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 1 ms 596 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 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 48 ms 55716 KB Output is correct
18 Correct 48 ms 55676 KB Output is correct
19 Correct 49 ms 55748 KB Output is correct
20 Correct 57 ms 55680 KB Output is correct
21 Correct 48 ms 55724 KB Output is correct
22 Correct 49 ms 55708 KB Output is correct
23 Correct 49 ms 55692 KB Output is correct
24 Correct 51 ms 55648 KB Output is correct
25 Correct 49 ms 55652 KB Output is correct
26 Correct 51 ms 55700 KB Output is correct
27 Correct 60 ms 55756 KB Output is correct
28 Correct 56 ms 55712 KB Output is correct
29 Correct 49 ms 55700 KB Output is correct
30 Correct 60 ms 55704 KB Output is correct
31 Correct 53 ms 55660 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 247 ms 57164 KB Output is correct
8 Correct 231 ms 59724 KB Output is correct
9 Correct 252 ms 59632 KB Output is correct
10 Correct 222 ms 59660 KB Output is correct
11 Correct 228 ms 59768 KB Output is correct
12 Correct 209 ms 59616 KB Output is correct
13 Correct 30 ms 4132 KB Output is correct
14 Correct 22 ms 1492 KB Output is correct
15 Correct 291 ms 60648 KB Output is correct
16 Correct 330 ms 60652 KB Output is correct
17 Correct 300 ms 60644 KB Output is correct
18 Correct 31 ms 4032 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 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 1 ms 596 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 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 48 ms 55716 KB Output is correct
18 Correct 48 ms 55676 KB Output is correct
19 Correct 49 ms 55748 KB Output is correct
20 Correct 57 ms 55680 KB Output is correct
21 Correct 48 ms 55724 KB Output is correct
22 Correct 49 ms 55708 KB Output is correct
23 Correct 49 ms 55692 KB Output is correct
24 Correct 51 ms 55648 KB Output is correct
25 Correct 49 ms 55652 KB Output is correct
26 Correct 51 ms 55700 KB Output is correct
27 Correct 60 ms 55756 KB Output is correct
28 Correct 56 ms 55712 KB Output is correct
29 Correct 49 ms 55700 KB Output is correct
30 Correct 60 ms 55704 KB Output is correct
31 Correct 53 ms 55660 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 247 ms 57164 KB Output is correct
39 Correct 231 ms 59724 KB Output is correct
40 Correct 252 ms 59632 KB Output is correct
41 Correct 222 ms 59660 KB Output is correct
42 Correct 228 ms 59768 KB Output is correct
43 Correct 209 ms 59616 KB Output is correct
44 Correct 30 ms 4132 KB Output is correct
45 Correct 22 ms 1492 KB Output is correct
46 Correct 291 ms 60648 KB Output is correct
47 Correct 330 ms 60652 KB Output is correct
48 Correct 300 ms 60644 KB Output is correct
49 Correct 31 ms 4032 KB Output is correct
50 Correct 766 ms 61764 KB Output is correct
51 Correct 648 ms 61760 KB Output is correct
52 Correct 535 ms 61824 KB Output is correct
53 Correct 594 ms 61820 KB Output is correct
54 Correct 521 ms 61816 KB Output is correct
55 Correct 558 ms 61932 KB Output is correct
56 Correct 207 ms 61640 KB Output is correct
57 Correct 194 ms 61632 KB Output is correct
58 Correct 190 ms 61648 KB Output is correct