oj.uz

Submission #846742

# Submission time Handle Problem Language Result Execution time Memory
846742 2023-09-08T10:54:06 Z lohacho Railway Trip (JOI17_railway_trip) C++14
100 / 100
 331 ms 103512 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 9048 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 1 ms 8796 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11100 KB Output is correct
2 Correct 81 ms 77064 KB Output is correct
3 Correct 86 ms 83284 KB Output is correct
4 Correct 90 ms 85224 KB Output is correct
5 Correct 88 ms 87376 KB Output is correct
6 Correct 91 ms 89684 KB Output is correct
7 Correct 108 ms 91216 KB Output is correct
8 Correct 35 ms 52376 KB Output is correct
9 Correct 63 ms 69728 KB Output is correct
10 Correct 50 ms 61488 KB Output is correct
11 Correct 70 ms 69456 KB Output is correct
12 Correct 68 ms 69436 KB Output is correct
13 Correct 70 ms 69200 KB Output is correct
14 Correct 71 ms 69564 KB Output is correct
15 Correct 67 ms 69456 KB Output is correct
16 Correct 66 ms 69248 KB Output is correct
17 Correct 96 ms 89684 KB Output is correct
18 Correct 95 ms 89912 KB Output is correct
19 Correct 94 ms 92240 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 80468 KB Output is correct
2 Correct 246 ms 78528 KB Output is correct
3 Correct 246 ms 82572 KB Output is correct
4 Correct 252 ms 85028 KB Output is correct
5 Correct 245 ms 84820 KB Output is correct
6 Correct 252 ms 85168 KB Output is correct
7 Correct 253 ms 84872 KB Output is correct
8 Correct 212 ms 61748 KB Output is correct
9 Correct 183 ms 53452 KB Output is correct
10 Correct 186 ms 53564 KB Output is correct
11 Correct 191 ms 53692 KB Output is correct
12 Correct 198 ms 53672 KB Output is correct
13 Correct 182 ms 53680 KB Output is correct
14 Correct 193 ms 53712 KB Output is correct
15 Correct 198 ms 53580 KB Output is correct
16 Correct 209 ms 59688 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 92792 KB Output is correct
2 Correct 280 ms 92500 KB Output is correct
3 Correct 253 ms 91448 KB Output is correct
4 Correct 267 ms 91568 KB Output is correct
5 Correct 192 ms 53668 KB Output is correct
6 Correct 265 ms 71728 KB Output is correct
7 Correct 247 ms 71252 KB Output is correct
8 Correct 242 ms 63080 KB Output is correct
9 Correct 261 ms 71152 KB Output is correct
10 Correct 264 ms 71128 KB Output is correct
11 Correct 242 ms 70736 KB Output is correct
12 Correct 237 ms 71528 KB Output is correct
13 Correct 257 ms 70992 KB Output is correct
14 Correct 298 ms 86144 KB Output is correct
15 Correct 296 ms 94036 KB Output is correct
16 Correct 331 ms 103512 KB Output is correct
17 Correct 275 ms 80208 KB Output is correct
18 Correct 267 ms 80724 KB Output is correct
19 Correct 260 ms 80944 KB Output is correct
20 Correct 244 ms 77260 KB Output is correct
21 Correct 282 ms 91368 KB Output is correct
22 Correct 262 ms 91152 KB Output is correct
23 Correct 265 ms 93680 KB Output is correct