Submission #1200188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200188		JooDdae	Railway Trip (JOI17_railway_trip)	C++20	0 / 100	59 ms	29628 KiB

railway_trip

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int INF = 1e6;

int n, k, q, m, a[100100], p[100100], rc[100100], lev[200200], sp[20][200200], d[20][200200][2][2];
vector<int> lc[100100], v[100100];
vector<array<int, 2>> e, ld[100100], rd[100100];

void dfs(int u) {
    sort(v[u].begin(), v[u].end());
    
    int pr = e[u][0], pc = 0;
    ld[u].push_back({e[u][0], 0});
    for(auto x : v[u]) {
        auto [pr, pc] = ld[u].back();
        ld[u].push_back({e[x][1], e[x][0]-pr+1 + pc});
        lev[x] = lev[u]+1, sp[0][x] = u;
        dfs(x);
    }

    rd[u].push_back({e[u][1], 0});
    for(int i=v[u].size()-1;i>=0;i--) {
        int x = v[u][i];
        auto [pl, pc] = rd[u].back();
        rd[u].push_back({e[x][0], pl-e[x][1]+1 + pc});
    }
    reverse(rd[u].begin(), rd[u].end());
}

int lca(int x, int y) {
    if(lev[x] < lev[y]) swap(x, y);
    for(int i=19;i>=0;i--) if((1 << i) & (lev[x]-lev[y])) x = sp[i][x];
    if(x == y) return x;
    for(int i=19;i>=0;i--) if(sp[i][x] != sp[i][y]) x = sp[i][x], y = sp[i][y];
    return sp[0][x];
}

int find_left(int u, int x) {
    auto it = *prev(upper_bound(ld[u].begin(), ld[u].end(), array<int, 2>({x, INF*10})));
    return it[1] + (x-it[0]);
}

int find_right(int u, int x) {
    auto it = *lower_bound(rd[u].begin(), rd[u].end(), array<int, 2>({x, 0}));
    return it[1] + (it[0]-x);
}

array<array<int, 4>, 2> lift(int h, int u, int x) {
    auto [l, r] = e[x];

    if(h < 0) {
        array<int, 4> re = {u, 0, find_left(x, u), find_right(x, u)};
        return {re, re};
    }
    
    int lc = u-l, rc = r-u;
    lc = min(lc, rc+1), rc = min(lc+1, rc);

    for(int i=19;i>=0;i--) if((1 << i) & h) {
        int L = min(lc + d[i][x][0][0], rc + d[i][x][1][0]), R = min(lc + d[i][x][0][1], rc + d[i][x][1][1]);
        lc = min(L, R+1), rc = min(L+1, R), x = sp[i][x];
    }

    auto LL = find_left(sp[0][x], e[x][1]);
    auto RR = find_right(sp[0][x], e[x][0]);
    return {array<int, 4>({e[x][0], lc, LL-1, RR}), {e[x][1], rc, LL, RR-1}};
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k >> q;
    for(int i=1;i<=n;i++) cin >> a[i];

    vector<int> s;
    for(int i=1;i<=n;i++) {
        while(!s.empty() && a[s.back()] <= a[i]) {
            e.push_back({s.back(), i}), s.pop_back();
        }
        s.push_back(i);
    }
    s.clear();

    for(int i=n;i>=1;i--) {
        while(!s.empty() && a[s.back()] <= a[i]) {
            e.push_back({i, s.back()}), s.pop_back();
        }
        s.push_back(i);
    }
    s.clear();

    e.push_back({-INF*2, INF*2});
    sort(e.begin(), e.end(), [&](auto &a, auto &b){ return tie(a[0], b[1]) < tie(b[0], a[1]); });
    e.erase(unique(e.begin(), e.end()), e.end());
    m = (int)e.size()-1;

    for(int i=1;i<=m;i++) {
        auto [l, r] = e[i];
        lc[l].push_back(i), rc[r]++;
    }

    s.push_back(0);
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=rc[i];j++) {
            int u = s.back(); s.pop_back();
            v[s.back()].push_back(u);
        }
        for(auto x : lc[i]) s.push_back(x);
        p[i] = s.back();
    }

    dfs(0);

    for(int i=0;i<20;i++) for(int j=1;j<=m;j++) for(int a=0;a<2;a++) for(int b=0;b<2;b++) d[i][j][a][b] = INF;

    for(int i=1;i<=m;i++) {
        auto [l, r] = e[i];
        auto [L, R] = e[sp[0][i]];

        d[0][i][0][0] = l-L;
        d[0][i][0][1] = R-r+1;
        d[0][i][1][0] = l-L+1;
        d[0][i][1][1] = R-r;
        for(int a=0;a<2;a++) for(int b=0;b<2;b++) d[0][i][a][b] = min(d[0][i][a][b], d[0][i][a][1-b]+1);
    }

    for(int i=1;i<20;i++) for(int j=1;j<=m;j++) {
        sp[i][j] = sp[i-1][sp[i-1][j]];
        for(int a=0;a<2;a++) for(int b=0;b<2;b++) for(int c=0;c<2;c++) {
            d[i][j][a][c] = min(d[i][j][a][c], d[i-1][j][a][b] + d[i-1][sp[i-1][j]][b][c]);
        }
        for(int a=0;a<2;a++) for(int b=0;b<2;b++) d[i][j][a][b] = min(d[i][j][a][b], d[i][j][a][1-b]+1);
    }

    while(q--) {
        int S, E; cin >> S >> E;
        if(S > E) swap(S, E);

        int ans = INF;
        for(int i=max(1, S-1);i<=S;i++) for(int j=E-1;j<=E;j++) {
            int P = lca(p[i], p[j]);
            
            auto L = lift(lev[p[i]]-lev[P]-1, S, p[i]);
            auto R = lift(lev[p[j]]-lev[P]-1, E, p[j]);

            // for(int i=0;i<2;i++) cout << L[i][0] << " " << L[i][1] << " " << L[i][2] << " " << L[i][3] << "\n";
            // for(int i=0;i<2;i++) cout << R[i][0] << " " << R[i][1] << " " << R[i][2] << " " << R[i][3] << "\n";

            for(int i=0;i<2;i++) for(int j=0;j<2;j++) {
                ans = min(ans, L[i][1]+R[j][1] + min(R[j][2]-L[i][2], R[j][3]+L[i][2]+1));
            }
        }
        cout << ans-1 << "\n";
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55