oj.uz

Submission #895385

# Submission time Handle Problem Language Result Execution time Memory
895385 2023-12-29T20:27:06 Z juliany2 Railway Trip 2 (JOI22_ho_t4) C++17
71 / 100
 172 ms 39012 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

template<class T> struct ST {
    static constexpr T ID = {{{(int) 1e9, 0}, {(int) -1e9, 0}}}; // or whatever ID
    inline T comb(T a, T b) { return {min(a[0], b[0]), max(a[1], b[1])}; } // or whatever function

    int sz;
    vector<T> t;

    void init(int _sz, T val = ID) {
        t.assign((sz = _sz) * 2, ID);
    }
    void init(vector<T> &v) {
        t.resize((sz = v.size()) * 2);
        for (int i = 0; i < sz; ++i)
            t[i + sz] = v[i];
        for (int i = sz - 1; i; --i)
            t[i] = comb(t[i * 2], t[(i * 2) | 1]);
    }
    void upd(int i, T x) {
        for (t[i += sz] = x; i > 1; i >>= 1)
            t[i >> 1] = comb(t[i], t[i ^ 1]);
    }
    T query(int l, int r) {
        T ql = ID, qr = ID;
        for (l += sz, r += sz + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ql = comb(ql, t[l++]);
            if (r & 1) qr = comb(t[--r], qr);
        }
        return comb(ql, qr);
    }
};

const int N = 1e5 + 7, L = 20;
int n, k, m;
int l[N], r[N];
int lift[N][L][2];
vector<int> x[N], y[N];

int main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> n >> k >> m;

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;

        if (a < b) {
            int s = min(b, a + k - 1);
            x[a].push_back(b);
            x[s + 1].push_back(-b);
        }
        else {
            int s = max(b, a - k + 1);
            y[s].push_back(b);
            y[a + 1].push_back(-b);
        }
    }

    iota(l + 1, l + n + 1, 1);
    iota(r + 1, r + n + 1, 1);

    ST<array<array<int, 2>, 2>> st;
    st.init(n + 1);

    multiset<int> X, Y;
    for (int i = 1; i <= n; i++) {
        for (int a : x[i]) {
            if (a > 0)
                X.insert(a);
            else
                X.erase(X.find(-a));
        }
        for (int a : y[i]) {
            if (a > 0)
                Y.insert(a);
            else
                Y.erase(Y.find(-a));
        }

        if (X.size())
            r[i] = *X.rbegin();
        if (Y.size())
            l[i] = *Y.begin();

        st.upd(i, {{{l[i], i}, {r[i], i}}});
    }

    for (int i = 1; i <= n; i++) {
        lift[i][0][0] = st.query(l[i], r[i])[0][1];
        lift[i][0][1] = st.query(l[i], r[i])[1][1];
    }

    for (int j = 1; j < L; j++) {
        for (int i = 1; i <= n; i++) {
            lift[i][j][0] = min(lift[lift[i][j - 1][0]][j - 1][0], lift[lift[i][j - 1][1]][j - 1][0]);
            lift[i][j][1] = max(lift[lift[i][j - 1][0]][j - 1][1], lift[lift[i][j - 1][1]][j - 1][1]);
        }
    }

    int q;
    cin >> q;

    while (q--) {
        int s, t;
        cin >> s >> t;

        if (t >= l[s] && t <= r[s]) {
            cout << 1 << '\n';
            continue;
        }

        int a = s, b = s, ans = 1;
        for (int i = L - 1; ~i; i--) {
            int na = min(lift[a][i][0], lift[b][i][0]), nb = max(lift[a][i][1], lift[b][i][1]);
            if (t < l[na] || t > r[nb])
                a = na, b = nb, ans += (1 << i);
        }

        int fa = min(lift[a][0][0], lift[b][0][0]), fb = max(lift[a][0][1], lift[b][0][1]);

        cout << (t >= l[fa] && t <= r[fb] ? ans + 1 : -1) << '\n';
    }

    return 0;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 8.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 28356 KB Output is correct
2 Correct 54 ms 28468 KB Output is correct
3 Correct 68 ms 28900 KB Output is correct
4 Correct 57 ms 28244 KB Output is correct
5 Correct 140 ms 34896 KB Output is correct
6 Correct 82 ms 33356 KB Output is correct
7 Correct 111 ms 38500 KB Output is correct
8 Correct 94 ms 31816 KB Output is correct
9 Correct 93 ms 32052 KB Output is correct
10 Correct 123 ms 32596 KB Output is correct
11 Correct 109 ms 32592 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 33620 KB Output is correct
2 Correct 160 ms 35660 KB Output is correct
3 Correct 78 ms 32848 KB Output is correct
4 Correct 120 ms 39012 KB Output is correct
5 Correct 172 ms 38176 KB Output is correct
6 Correct 159 ms 37712 KB Output is correct
7 Correct 113 ms 33124 KB Output is correct
8 Correct 134 ms 33284 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 34168 KB Output is correct
2 Correct 79 ms 29776 KB Output is correct
3 Correct 70 ms 27540 KB Output is correct
4 Correct 52 ms 26192 KB Output is correct
5 Correct 44 ms 25684 KB Output is correct
6 Correct 44 ms 25424 KB Output is correct
7 Correct 87 ms 34756 KB Output is correct
8 Correct 2 ms 8792 KB Output is correct
9 Correct 3 ms 8912 KB Output is correct
10 Correct 152 ms 34296 KB Output is correct
11 Correct 149 ms 36384 KB Output is correct
12 Correct 157 ms 34388 KB Output is correct
13 Correct 150 ms 36180 KB Output is correct
14 Correct 2 ms 8792 KB Output is correct
15 Correct 3 ms 8796 KB Output is correct
16 Correct 85 ms 31192 KB Output is correct
17 Correct 112 ms 31916 KB Output is correct
18 Correct 111 ms 31940 KB Output is correct
19 Correct 112 ms 31828 KB Output is correct

Subtask #6
0 / 13.0

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