oj.uz

Submission #846755

# Submission time Handle Problem Language Result Execution time Memory
846755 2023-09-08T11:29:13 Z lohacho Railway Trip (JOI17_railway_trip) C++14
100 / 100
 242 ms 94740 KB 
#include <bits/stdc++.h>
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][17][4], 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 i, j;
 
    int n, k, q;
    cin >> n >> k >> q;
    a[0] = a[n + 1] = k + 1;
    for(i = 1; i <= n; ++i){
        cin >> a[i];
    }
    n += 2;
    build(1, 0, n - 1);
    for(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] = min(i, (int)id.size() - i + 2);
            spa[tn][0][1] = min(i + 1, (int)id.size() - i + 1);
            spa[tn][0][2] = min(i + 1, (int)id.size() - i + 1);
            spa[tn][0][3] = 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(j = 1; j < 17; ++j){
        for(i = 0; i <= tn; ++i){
            pr[i][j] = pr[pr[i][j - 1]][j - 1];
            spa[i][j][0] = min(spa[i][j - 1][0] + spa[pr[i][j - 1]][j - 1][0], spa[i][j - 1][1] + spa[pr[i][j - 1]][j - 1][2]);
            spa[i][j][1] = min(spa[i][j - 1][0] + spa[pr[i][j - 1]][j - 1][1], spa[i][j - 1][1] + spa[pr[i][j - 1]][j - 1][3]);
            spa[i][j][2] = min(spa[i][j - 1][2] + spa[pr[i][j - 1]][j - 1][0], spa[i][j - 1][3] + spa[pr[i][j - 1]][j - 1][2]);
            spa[i][j][3] = min(spa[i][j - 1][2] + spa[pr[i][j - 1]][j - 1][1], spa[i][j - 1][3] + spa[pr[i][j - 1]][j - 1][3]);
        }
    }
 
    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(i = 16; i >= 0; --i){
            if(dep[y] - (1 << i) >= dep[x]){
                int nvyf = min(vyf + spa[y][i][0], vys + spa[y][i][2]), nvys = min(vyf + spa[y][i][1], vys + spa[y][i][3]);
                vyf = nvyf, vys = nvys;
                y = pr[y][i];
            }
        }
 
        for(i = 16; i >= 0; --i){
            if(pr[x][i] != pr[y][i]){
                int nvyf = min(vyf + spa[y][i][0], vys + spa[y][i][2]), nvys = min(vyf + spa[y][i][1], vys + spa[y][i][3]);
                vyf = nvyf, vys = nvys;
                y = pr[y][i];
                
                int nvxf = min(vxf + spa[x][i][0], vxs + spa[x][i][2]), nvxs = min(vxf + spa[x][i][1], vxs + spa[x][i][3]);
                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] + vys + spa[y][0][3] + 1);
                ans = min(ans, vxs + spa[x][0][3] + vyf + spa[y][0][0] + 1);
            }
        }
 
        cout << ans - 1 << '\n';
    }
    
    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 8792 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 2 ms 8792 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8792 KB Output is correct
8 Correct 1 ms 8792 KB Output is correct
9 Correct 1 ms 8796 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11248 KB Output is correct
2 Correct 77 ms 68924 KB Output is correct
3 Correct 82 ms 75160 KB Output is correct
4 Correct 85 ms 77136 KB Output is correct
5 Correct 86 ms 79184 KB Output is correct
6 Correct 84 ms 79320 KB Output is correct
7 Correct 103 ms 80464 KB Output is correct
8 Correct 41 ms 46172 KB Output is correct
9 Correct 62 ms 64348 KB Output is correct
10 Correct 52 ms 55860 KB Output is correct
11 Correct 68 ms 63568 KB Output is correct
12 Correct 66 ms 63564 KB Output is correct
13 Correct 69 ms 63568 KB Output is correct
14 Correct 64 ms 63824 KB Output is correct
15 Correct 67 ms 63568 KB Output is correct
16 Correct 67 ms 63312 KB Output is correct
17 Correct 93 ms 79184 KB Output is correct
18 Correct 93 ms 79184 KB Output is correct
19 Correct 91 ms 81768 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 71248 KB Output is correct
2 Correct 124 ms 69200 KB Output is correct
3 Correct 134 ms 73296 KB Output is correct
4 Correct 144 ms 75344 KB Output is correct
5 Correct 132 ms 75344 KB Output is correct
6 Correct 133 ms 75560 KB Output is correct
7 Correct 136 ms 75344 KB Output is correct
8 Correct 89 ms 56628 KB Output is correct
9 Correct 79 ms 46456 KB Output is correct
10 Correct 81 ms 46284 KB Output is correct
11 Correct 77 ms 46224 KB Output is correct
12 Correct 76 ms 46280 KB Output is correct
13 Correct 79 ms 46280 KB Output is correct
14 Correct 85 ms 46372 KB Output is correct
15 Correct 80 ms 48348 KB Output is correct
16 Correct 96 ms 52428 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 80976 KB Output is correct
2 Correct 155 ms 80976 KB Output is correct
3 Correct 145 ms 79684 KB Output is correct
4 Correct 159 ms 79952 KB Output is correct
5 Correct 74 ms 46280 KB Output is correct
6 Correct 159 ms 65104 KB Output is correct
7 Correct 147 ms 65012 KB Output is correct
8 Correct 125 ms 56872 KB Output is correct
9 Correct 129 ms 64092 KB Output is correct
10 Correct 132 ms 63916 KB Output is correct
11 Correct 145 ms 63824 KB Output is correct
12 Correct 134 ms 64092 KB Output is correct
13 Correct 139 ms 64356 KB Output is correct
14 Correct 206 ms 77904 KB Output is correct
15 Correct 206 ms 86572 KB Output is correct
16 Correct 242 ms 94740 KB Output is correct
17 Correct 179 ms 71504 KB Output is correct
18 Correct 157 ms 72052 KB Output is correct
19 Correct 168 ms 72272 KB Output is correct
20 Correct 138 ms 67748 KB Output is correct
21 Correct 146 ms 79440 KB Output is correct
22 Correct 149 ms 79696 KB Output is correct
23 Correct 161 ms 82048 KB Output is correct