Submission #964040

#	Time	Username	Problem	Language	Result	Execution time	Memory
964040		RaresFelix	Bitaro's travel (JOI23_travel)	C++17	100 / 100	183 ms	70708 KiB

travel

#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")

#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
#define int ll 
using ll = long long;
using ld = long double;  // or double, if TL is tight
using str = string; 
using ii = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;

const int INF = 1e9;

struct RMQmax {
    int n;
    vector<vi> M;

    RMQmax(vi V) {
        n = V.size();
        M.push_back(V);
        for(int k = 1; (1 << k) <= n; ++k) {
            M.push_back(M.back());
            for(int i = 0; i < n; ++i)
                if(i + (1 << (k - 1)) < n)
                    M[k][i] = max(M[k][i], M[k - 1][i + (1 << (k - 1))]);
        }
    }

    int query(int p, int k) {
        return M[k][p];
    }
};

struct RMQmin {
    int n;
    vector<vi> M;

    RMQmin(vi V) {
        n = V.size();
        M.push_back(V);
        for(int k = 1; (1 << k) <= n; ++k) {
            M.push_back(M.back());
            for(int i = 0; i < n; ++i)
                if(i + (1 << (k - 1)) < n)
                    M[k][i] = min(M[k][i], M[k - 1][i + (1 << (k - 1))]);
        }
    }

    int query(int p, int k) {
        return M[k][p];
    }
};

signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    ///TODO long long

    int n;
    cin >> n;

    vi V(n), Dif1(n), Dif2(n), DP(n, 0);

    for(int i = 0; i < n; ++i)
        cin >> V[i];

    for(int i = 0; i + 1 < n; ++i) Dif1[i] = 2 * V[i] - V[i + 1];
    Dif1[n - 1] = INF;
    RMQmin QD1(Dif1);
    
    for(int i = 1; i < n; ++i) Dif2[i] = 2 * V[i] - V[i - 1];
    Dif2[0] = INF;
    RMQmax QD2(Dif2);

    for(int i = 0; i < n; ++i) {
        DP[i] = 0;
        int st = i, dr = i, dir = 0;
        ///dir: 0 pt st, 1 pt dr
        if(i == 0 || i == n - 1) {
            dir = !i;
        } else {
            if(V[i] - V[i - 1] <= V[i + 1] - V[i]) dir = 0;
            else dir = 1;
        }
        while(st != 0 || dr != n - 1) {
            if((!dir && st == 0) || (dir && dr == n - 1)) {
                DP[i] += V[dr] - V[st];
                dir ^= 1;
            }
            if(dir) {
                if(st == 0) {
                    DP[i] += V.back() - V[dr];
                    dr = n - 1;
                    break;
                }
                int dr0 = dr;
                for(int k = (int)QD1.M.size() - 1; k >= 0; --k) {
                    if(dr + (1 << k) >= n) continue;
                    if(QD1.query(dr, k) > V[st - 1]) {
                        dr += (1 << k);
                    } 
                }
                DP[i] += V[dr] - V[dr0];
                dir ^= 1;
                DP[i] += V[dr] - V[st];
            } else {
                if(dr == n - 1) {
                    DP[i] += V[st] - V[0];
                    st = 0;
                    break;
                }
                int st0 = st;
                for(int k = (int)QD2.M.size() - 1; k >= 0; --k) {
                    if(st - (1 << k) < 0) continue;
                    if(QD2.query(st - (1 << k) + 1, k) <= V[dr + 1])
                        st -= (1 << k);
                }
                DP[i] += V[st0] - V[st];
                dir ^= 1;
                DP[i] += V[dr] - V[st];
            }
        }
    }
    int q;
    cin >> q;
    for(int i = 0; i < q; ++i) {
        int p;
        cin >> p;
        int st = 0, dr = n - 1, mij;
        while(st < dr) {
            mij = (st + dr + 1) / 2;
            if(V[mij] > p) dr = mij - 1;
            else st = mij;
        }
        int id = 0, cre = 2e9;
        for(int j = max(st - 1, 0ll); j <= min(n - 1, st + 1); ++j)
            if(abs(V[j] - p) < cre) {
                cre = abs(V[j] - p);
                id = j;
            }
        cout << cre + DP[id] << "\n";
    }
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 55 / 55