oj.uz

Submission #691358

# Submission time Handle Problem Language Result Execution time Memory
691358 2023-01-31T06:02:06 Z tengiz05 Railway Trip (JOI17_railway_trip) C++17
20 / 100
 877 ms 64568 KB 
#include <bits/stdc++.h>

using namespace std;

struct Node {
    int s = 0;
    Node *l = nullptr;
    Node *r = nullptr;
};
Node *add(Node *t, int l, int r, int x) {
    Node *nt = new Node();
    if (t != nullptr) {
        *nt = *t;
    }
    nt->s++;
    if (r - l > 1) {
        int m = (l + r) / 2;
        if (x < m) {
            nt->l = add(nt->l, l, m, x);
        } else {
            nt->r = add(nt->r, m, r, x);
        }
    }
    return nt;
}
int query(Node *t1, Node *t2, int l, int r, int x, int y) {
    if (r <= x || y <= l) {
        return 0;
    }
    if (x <= l && r <= y) {
        return (t2 ? t2->s : 0) - (t1 ? t1->s : 0);
    }
    int m = (l + r) / 2;
    return query(t1 ? t1->l : nullptr, t2 ? t2->l : nullptr, l, m, x, y)
         + query(t1 ? t1->r : nullptr, t2 ? t2->r : nullptr, m, r, x, y);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k, q;
    cin >> n >> k >> q;
    
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }
    
    vector<Node *> root(n + 1, nullptr);
    for (int i = 0; i < n; i++) {
        root[i + 1] = add(root[i], 0, k, a[i]);
    }
    
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&](int i, int j) {
        return a[i] > a[j];
    });
    
    if (q <= 50) {
        vector<vector<int>> e(n);
        for (int i = 0; i < n; i++) {
            { // to the left
                int lo = -1, hi = i;
                while (lo + 1 < hi) {
                    int m = (lo + hi) / 2;
                    if (query(root[m], root[i], 0, k, a[i], k)) {
                        lo = m;
                    } else {
                        hi = m;
                    }
                }
                if (lo != -1) {
                    e[i].push_back(lo);
                    e[lo].push_back(i);
                }
            } { // to the right
                int lo = i, hi = n;
                while (lo + 1 < hi) {
                    int m = (lo + hi) / 2;
                    if (query(root[i + 1], root[m + 1], 0, k, a[i], k)) {
                        hi = m;
                    } else {
                        lo = m;
                    }
                }
                if (hi != n) {
                    e[i].push_back(hi);
                    e[hi].push_back(i);
                }
            }
        }
        while (q--) {
            int x, y;
            cin >> x >> y;
            x--;
            y--;
            if (x > y) swap(x, y);
            
            vector<int> dis(n, 1E9);
            dis[x] = 0;
            queue<int> q;
            q.push(x);
            while (!q.empty()) {
                auto u = q.front();
                q.pop();
                for (int v : e[u]) {
                    if (dis[v] > dis[u] + 1) {
                        dis[v] = dis[u] + 1;
                        q.push(v);
                    }
                }
            }
            cout << dis[y] - 1 << "\n";
        }
    }
    
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 708 KB Output is correct
2 Correct 241 ms 22456 KB Output is correct
3 Correct 264 ms 25528 KB Output is correct
4 Correct 335 ms 29672 KB Output is correct
5 Correct 393 ms 32836 KB Output is correct
6 Correct 524 ms 43132 KB Output is correct
7 Correct 877 ms 64568 KB Output is correct
8 Correct 159 ms 61068 KB Output is correct
9 Correct 505 ms 64296 KB Output is correct
10 Correct 343 ms 56012 KB Output is correct
11 Correct 632 ms 64184 KB Output is correct
12 Correct 605 ms 60048 KB Output is correct
13 Correct 558 ms 56940 KB Output is correct
14 Correct 615 ms 64192 KB Output is correct
15 Correct 596 ms 60064 KB Output is correct
16 Correct 547 ms 56912 KB Output is correct
17 Correct 593 ms 64404 KB Output is correct
18 Correct 547 ms 64420 KB Output is correct
19 Correct 593 ms 64412 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 17108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 57280 KB Output isn't correct
2 Halted 0 ms 0 KB -