oj.uz

Submission #846752

# Submission time Handle Problem Language Result Execution time Memory
846752 2023-09-08T11:28:12 Z lohacho Railway Trip (JOI17_railway_trip) C++14
100 / 100
 201 ms 91728 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][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 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 1 ms 8792 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 1 ms 8792 KB Output is correct
6 Correct 2 ms 8792 KB Output is correct
7 Correct 1 ms 8796 KB Output is correct
8 Correct 2 ms 8792 KB Output is correct
9 Correct 1 ms 8792 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB Output is correct
2 Correct 72 ms 68688 KB Output is correct
3 Correct 79 ms 75160 KB Output is correct
4 Correct 81 ms 77144 KB Output is correct
5 Correct 83 ms 79184 KB Output is correct
6 Correct 85 ms 79316 KB Output is correct
7 Correct 95 ms 80464 KB Output is correct
8 Correct 39 ms 46172 KB Output is correct
9 Correct 64 ms 63064 KB Output is correct
10 Correct 51 ms 55096 KB Output is correct
11 Correct 65 ms 63056 KB Output is correct
12 Correct 69 ms 62980 KB Output is correct
13 Correct 63 ms 62800 KB Output is correct
14 Correct 64 ms 63056 KB Output is correct
15 Correct 62 ms 62800 KB Output is correct
16 Correct 64 ms 62800 KB Output is correct
17 Correct 88 ms 79296 KB Output is correct
18 Correct 91 ms 79572 KB Output is correct
19 Correct 87 ms 81500 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 71280 KB Output is correct
2 Correct 123 ms 69200 KB Output is correct
3 Correct 129 ms 73192 KB Output is correct
4 Correct 130 ms 75448 KB Output is correct
5 Correct 134 ms 75344 KB Output is correct
6 Correct 135 ms 75488 KB Output is correct
7 Correct 134 ms 75584 KB Output is correct
8 Correct 90 ms 56624 KB Output is correct
9 Correct 76 ms 46600 KB Output is correct
10 Correct 81 ms 46284 KB Output is correct
11 Correct 74 ms 46276 KB Output is correct
12 Correct 80 ms 46280 KB Output is correct
13 Correct 75 ms 46280 KB Output is correct
14 Correct 77 ms 46276 KB Output is correct
15 Correct 86 ms 48124 KB Output is correct
16 Correct 95 ms 52456 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 80980 KB Output is correct
2 Correct 159 ms 80984 KB Output is correct
3 Correct 134 ms 79808 KB Output is correct
4 Correct 137 ms 79952 KB Output is correct
5 Correct 84 ms 46532 KB Output is correct
6 Correct 139 ms 63568 KB Output is correct
7 Correct 128 ms 63568 KB Output is correct
8 Correct 118 ms 56076 KB Output is correct
9 Correct 128 ms 63476 KB Output is correct
10 Correct 139 ms 63300 KB Output is correct
11 Correct 129 ms 63096 KB Output is correct
12 Correct 127 ms 63568 KB Output is correct
13 Correct 128 ms 63464 KB Output is correct
14 Correct 175 ms 76324 KB Output is correct
15 Correct 197 ms 84304 KB Output is correct
16 Correct 201 ms 91728 KB Output is correct
17 Correct 172 ms 70492 KB Output is correct
18 Correct 149 ms 71252 KB Output is correct
19 Correct 148 ms 71248 KB Output is correct
20 Correct 134 ms 67680 KB Output is correct
21 Correct 149 ms 79580 KB Output is correct
22 Correct 155 ms 79512 KB Output is correct
23 Correct 154 ms 81744 KB Output is correct