Submission #846742

#	Time	Username	Problem	Language	Result	Execution time	Memory
846742		lohacho	Railway Trip (JOI17_railway_trip)	C++14	100 / 100	331 ms	103512 KiB

railway_trip

#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
using namespace std;
 
const int NS = (int)1e5 + 4, SZ = (int)3e5 + 4;
int a[NS + 4];
int seg[NS * 4 + 4];
int spa[SZ][20][2][2], dep[SZ], lcnt[SZ], pr[SZ][20];
int st[NS];
vector<int> pos[NS];
void build(int x, int s, int e){
    if(s == e){
        seg[x] = a[s];
        return;
    }
    int m = s + e >> 1;
    build(x * 2, s, m);
    build(x * 2 + 1, m + 1, e);
    seg[x] = max(seg[x * 2], seg[x * 2 + 1]);
}
 
int get(int x, int s, int e, int fs, int fe){
    if(fe < s || fs > e || fs > fe) return -1;
    if(fs <= s && fe >= e){
        return seg[x];
    }
    int m = s + e >> 1;
    return max(get(x * 2, s, m, fs, fe), get(x * 2 + 1, m + 1, e, fs, fe));
}
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n, k, q;
    cin >> n >> k >> q;
    a[0] = a[n + 1] = k + 1;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    n += 2;
    build(1, 0, n - 1);
    for(int i = 0; i < n; ++i){
        pos[a[i]].push_back(i);
    }
 
    int tn = 0;
    auto gen = [&](auto&&self, int x, int s, int e)->void{
        if(s + 1 >= e){
            st[s] = x;
            return;
        }
        int mx = get(1, 0, n - 1, s + 1, e - 1);
 
        vector<int> id;
        int now = s;
        while(true){
            now = lower_bound(pos[mx].begin(), pos[mx].end(), now + 1) - pos[mx].begin();
            if(now < (int)pos[mx].size() && pos[mx][now] < e){
                now = pos[mx][now];
                id.push_back(now);
            }
            else break;
        }
 
        for(int i = 0; i <= (int)id.size(); ++i){
            ++tn;
            dep[tn] = dep[x] + 1;
            lcnt[tn] = i;
            pr[tn][0] = x;
            spa[tn][0][0][0] = min(i, (int)id.size() - i + 2);
            spa[tn][0][0][1] = min(i + 1, (int)id.size() - i + 1);
            spa[tn][0][1][0] = min(i + 1, (int)id.size() - i + 1);
            spa[tn][0][1][1] = min(i + 2, (int)id.size() - i);
 
            self(self, tn, (i ? id[i - 1] : s), (i < (int)id.size() ? id[i] : e));
        }
    };
    gen(gen, 0, 0, n - 1);
 
    for(int j = 1; j < 20; ++j){
        for(int i = 0; i <= tn; ++i){
            pr[i][j] = pr[pr[i][j - 1]][j - 1];
            spa[i][j][0][0] = min(spa[i][j - 1][0][0] + spa[pr[i][j - 1]][j - 1][0][0], spa[i][j - 1][0][1] + spa[pr[i][j - 1]][j - 1][1][0]);
            spa[i][j][0][1] = min(spa[i][j - 1][0][0] + spa[pr[i][j - 1]][j - 1][0][1], spa[i][j - 1][0][1] + spa[pr[i][j - 1]][j - 1][1][1]);
            spa[i][j][1][0] = min(spa[i][j - 1][1][0] + spa[pr[i][j - 1]][j - 1][0][0], spa[i][j - 1][1][1] + spa[pr[i][j - 1]][j - 1][1][0]);
            spa[i][j][1][1] = min(spa[i][j - 1][1][0] + spa[pr[i][j - 1]][j - 1][0][1], spa[i][j - 1][1][1] + spa[pr[i][j - 1]][j - 1][1][1]);
        }
    }
 
    while(q--){
        int x, y;
        cin >> x >> y;
        x = st[x], y = st[y];
        
        if(dep[x] > dep[y]){
            swap(x, y);
        }

        int vxf = 0, vxs = 1;
        int vyf = 0, vys = 1;
        for(int i = 19; i >= 0; --i){
            if(dep[y] - (1 << i) >= dep[x]){
                int nvyf = min(vyf + spa[y][i][0][0], vys + spa[y][i][1][0]), nvys = min(vyf + spa[y][i][0][1], vys + spa[y][i][1][1]);
                vyf = nvyf, vys = nvys;
                y = pr[y][i];
            }
        }
 
        for(int i = 19; i >= 0; --i){
            if(pr[x][i] != pr[y][i]){
                int nvyf = min(vyf + spa[y][i][0][0], vys + spa[y][i][1][0]), nvys = min(vyf + spa[y][i][0][1], vys + spa[y][i][1][1]);
                vyf = nvyf, vys = nvys;
                y = pr[y][i];
                
                int nvxf = min(vxf + spa[x][i][0][0], vxs + spa[x][i][1][0]), nvxs = min(vxf + spa[x][i][0][1], vxs + spa[x][i][1][1]);
                vxf = nvxf, vxs = nvxs;
                x = pr[x][i];
            }
        }
 
        int ans;
        if(x == y) ans = min(vxf + vyf, vxs + vys);
        else{
            if(lcnt[x] < lcnt[y]) ans = vxs + vyf + lcnt[y] - lcnt[x] - 1;
            else ans = vxf + vys + lcnt[x] - lcnt[y] - 1;
            if(pr[x][0] > 0){
                ans = min(ans, vxf + spa[x][0][0][0] + vys + spa[y][0][1][1] + 1);
                ans = min(ans, vxs + spa[x][0][1][1] + vyf + spa[y][0][0][0] + 1);
            }
        }
 
        cout << ans - 1 << endl;
    }
    
    return 0;
}

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