Submission #691358

#	Time	Username	Problem	Language	Result	Execution time	Memory
691358		tengiz05	Railway Trip (JOI17_railway_trip)	C++17	20 / 100	877 ms	64568 KiB

railway_trip

#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 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55