oj.uz

Submission #846754

# Submission time Handle Problem Language Result Execution time Memory
846754 2023-09-08T11:28:59 Z lohacho Railway Trip (JOI17_railway_trip) C++14
100 / 100
 227 ms 91672 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
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 1 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 8796 KB Output is correct
6 Correct 1 ms 9048 KB Output is correct
7 Correct 1 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 11096 KB Output is correct
2 Correct 71 ms 68724 KB Output is correct
3 Correct 78 ms 75136 KB Output is correct
4 Correct 86 ms 77148 KB Output is correct
5 Correct 86 ms 79136 KB Output is correct
6 Correct 77 ms 79308 KB Output is correct
7 Correct 95 ms 80464 KB Output is correct
8 Correct 39 ms 46172 KB Output is correct
9 Correct 55 ms 63256 KB Output is correct
10 Correct 54 ms 55136 KB Output is correct
11 Correct 67 ms 63056 KB Output is correct
12 Correct 69 ms 62800 KB Output is correct
13 Correct 65 ms 62804 KB Output is correct
14 Correct 69 ms 63316 KB Output is correct
15 Correct 66 ms 62812 KB Output is correct
16 Correct 66 ms 62860 KB Output is correct
17 Correct 86 ms 79188 KB Output is correct
18 Correct 88 ms 79184 KB Output is correct
19 Correct 86 ms 81484 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 71248 KB Output is correct
2 Correct 124 ms 69364 KB Output is correct
3 Correct 141 ms 73452 KB Output is correct
4 Correct 134 ms 75400 KB Output is correct
5 Correct 132 ms 75344 KB Output is correct
6 Correct 136 ms 75372 KB Output is correct
7 Correct 135 ms 75348 KB Output is correct
8 Correct 105 ms 56792 KB Output is correct
9 Correct 76 ms 46288 KB Output is correct
10 Correct 87 ms 46280 KB Output is correct
11 Correct 77 ms 46456 KB Output is correct
12 Correct 75 ms 46284 KB Output is correct
13 Correct 77 ms 46284 KB Output is correct
14 Correct 83 ms 46288 KB Output is correct
15 Correct 83 ms 48200 KB Output is correct
16 Correct 99 ms 52428 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 80976 KB Output is correct
2 Correct 153 ms 80976 KB Output is correct
3 Correct 142 ms 79812 KB Output is correct
4 Correct 135 ms 80084 KB Output is correct
5 Correct 84 ms 46420 KB Output is correct
6 Correct 135 ms 63828 KB Output is correct
7 Correct 145 ms 63792 KB Output is correct
8 Correct 112 ms 55596 KB Output is correct
9 Correct 136 ms 63568 KB Output is correct
10 Correct 138 ms 63452 KB Output is correct
11 Correct 127 ms 63108 KB Output is correct
12 Correct 152 ms 63568 KB Output is correct
13 Correct 155 ms 63532 KB Output is correct
14 Correct 186 ms 76324 KB Output is correct
15 Correct 203 ms 84308 KB Output is correct
16 Correct 227 ms 91672 KB Output is correct
17 Correct 171 ms 70460 KB Output is correct
18 Correct 176 ms 71260 KB Output is correct
19 Correct 161 ms 71432 KB Output is correct
20 Correct 134 ms 67684 KB Output is correct
21 Correct 144 ms 79596 KB Output is correct
22 Correct 150 ms 79600 KB Output is correct
23 Correct 140 ms 81744 KB Output is correct