oj.uz

Submission #792500

# Submission time Handle Problem Language Result Execution time Memory
792500 2023-07-25T06:02:21 Z vjudge1 Bitaro's travel (JOI23_travel) C++17
0 / 100
 229 ms 58104 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));
            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 a, ll b) {return (a > b ? a : b);});
    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
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 Incorrect 1 ms 596 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
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 Incorrect 1 ms 596 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 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 Incorrect 229 ms 58104 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 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 Incorrect 1 ms 596 KB Output isn't correct
6 Halted 0 ms 0 KB -