oj.uz

Submission #594090

# Submission time Handle Problem Language Result Execution time Memory
594090 2022-07-12T05:16:43 Z piOOE Railway Trip 2 (JOI22_ho_t4) C++17
100 / 100
 366 ms 258188 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

template<typename T>
struct SparseTableMax { //max
    int n;
    vector<vector<T>> st;

    SparseTableMax(const vector<T> &a) {
        init(a);
    }

    void init(const vector<T>& a) {
        n = static_cast<int>(a.size());
        int max_log = 32 - __builtin_clz(n);
        st.resize(max_log);
        st[0] = a;
        for (int j = 1; j < max_log; ++j) {
            st[j].resize(n - (1 << j) + 1);
            for (int i = 0; i <= n - (1 << j); ++i) {
                st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
            }
        }
    }

    SparseTableMax() = default;

    T get(int L, int R) const {
        assert(0 <= L && L < R && R <= n);
        int lg = __lg(R - L);
        return max(st[lg][L], st[lg][R - (1 << lg)]);
    }
};

template <typename T>
struct SparseTableMin { //min
    int n;
    vector<vector<T>> st;

    SparseTableMin(const vector<T>& a) {
        init(a);
    }

    void init(const vector<T>& a) {
        n = static_cast<int>(a.size());
        int max_log = 32 - __builtin_clz(n);
        st.resize(max_log);
        st[0] = a;
        for (int j = 1; j < max_log; ++j) {
            st[j].resize(n - (1 << j) + 1);
            for (int i = 0; i <= n - (1 << j); ++i) {
                st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
            }
        }
    }

    SparseTableMin() = default;

    T get(int L, int R) const {
        assert(0 <= L && L < R && R <= n);
        int lg = __lg(R - L);
        return min(st[lg][L], st[lg][R - (1 << lg)]);
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k, m;
    cin >> n >> k >> m;
    vector<vector<int>> qu(n);
    vector<pair<int, int>> b(m);
    for (int i = 0; i < m; ++i) {
        cin >> b[i].first >> b[i].second;
        --b[i].first, --b[i].second;
    }
    //from left to right
    for (int i = 0; i < m; ++i) {
        if (b[i].first < b[i].second) {
            qu[b[i].first].push_back(b[i].second);
            int r = min(b[i].first + k, b[i].second);
            qu[r].push_back(~b[i].second);
        }
    }
    int logn = 20;
    vector<vector<int>> R(logn, vector<int>(n)), L(logn, vector<int>(n));
    multiset<int, greater<>> st1;
    for (int i = 0; i < n; ++i) {
        for (int r : qu[i]) {
            if (r >= 0) {
                st1.insert(r);
            } else {
                st1.extract(~r);
            }
        }
        qu[i].clear();
        if (st1.empty()) {
            R[0][i] = i;
        } else {
            R[0][i] = *st1.begin();
        }
    }
    //from right to left
    for (int i = 0; i < m; ++i) {
        if (b[i].first > b[i].second) {
            qu[b[i].first].push_back(b[i].second);
            int l = max(b[i].second, b[i].first - k);
            qu[l].push_back(~b[i].second);
        }
    }
    multiset<int> st2;
    for (int i = n - 1; i > -1; --i) {
        for (int l : qu[i]) {
            if (l >= 0) {
                st2.insert(l);
            } else {
                st2.extract(~l);
            }
        }
        qu[i].clear();
        if (st2.empty()) {
            L[0][i] = i;
        } else {
            L[0][i] = *st2.begin();
        }
    }
    //calc binups
    SparseTableMax<int> stR[logn];
    SparseTableMin<int> stL[logn];
    for (int j = 1; j < logn; ++j) {
        stR[j - 1].init(R[j - 1]);
        stL[j - 1].init(L[j - 1]);
        for (int i = 0; i < n; ++i) {
            L[j][i] = stL[j - 1].get(L[j - 1][i], R[j - 1][i] + 1);
            R[j][i] = stR[j - 1].get(L[j - 1][i], R[j - 1][i] + 1);
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int s, t;
        cin >> s >> t;
        --s, --t;
        if (s < t) {
            if (R[logn - 1][s] < t) {
                cout << "-1\n";
                continue;
            }
            int ans = 0;
            int l = s, r = s;
            for (int j = logn - 1; j > -1; --j) {
                if (R[j][s] < t) {
                    ans += 1 << j;
                    r = R[j][s];
                    l = L[j][s];
                    break;
                }
            }
            for (int j = logn - 2; j > -1; --j) {
                if (stR[j].get(l, r + 1) < t) {
                    int rr = stR[j].get(l, r + 1);
                    int ll = stL[j].get(l, r + 1);
                    r = rr, l = ll;
                    ans += 1 << j;
                }
            }
            cout << ans + 1 << '\n';
        } else {
            if (L[logn - 1][s] > t) {
                cout << "-1\n";
                continue;
            }
            int ans = 0;
            int l = s, r = s;
            for (int j = logn - 1; j > -1; --j) {
                if (L[j][s] > t) {
                    ans += 1 << j;
                    r = R[j][s];
                    l = L[j][s];
                    break;
                }
            }
            for (int j = logn - 2; j > -1; --j) {
                if (stL[j].get(l, r + 1) > t) {
                    int rr = stR[j].get(l, r + 1);
                    int ll = stL[j].get(l, r + 1);
                    r = rr, l = ll;
                    ans += 1 << j;
                }
            }
            cout << ans + 1 << '\n';
        }
    }
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 704 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 2 ms 708 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 704 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 2 ms 708 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 5 ms 3668 KB Output is correct
14 Correct 5 ms 3756 KB Output is correct
15 Correct 3 ms 3720 KB Output is correct
16 Correct 5 ms 3668 KB Output is correct
17 Correct 4 ms 3668 KB Output is correct
18 Correct 7 ms 3796 KB Output is correct
19 Correct 4 ms 3528 KB Output is correct
20 Correct 5 ms 3668 KB Output is correct
21 Correct 4 ms 3668 KB Output is correct
22 Correct 5 ms 3756 KB Output is correct
23 Correct 5 ms 3668 KB Output is correct
24 Correct 6 ms 3732 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 255392 KB Output is correct
2 Correct 204 ms 255360 KB Output is correct
3 Correct 205 ms 255556 KB Output is correct
4 Correct 180 ms 255164 KB Output is correct
5 Correct 271 ms 257352 KB Output is correct
6 Correct 213 ms 256612 KB Output is correct
7 Correct 287 ms 257660 KB Output is correct
8 Correct 223 ms 253056 KB Output is correct
9 Correct 224 ms 255648 KB Output is correct
10 Correct 252 ms 256664 KB Output is correct
11 Correct 228 ms 256644 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 255316 KB Output is correct
2 Correct 340 ms 257356 KB Output is correct
3 Correct 250 ms 255996 KB Output is correct
4 Correct 328 ms 257760 KB Output is correct
5 Correct 307 ms 254744 KB Output is correct
6 Correct 298 ms 257164 KB Output is correct
7 Correct 329 ms 256764 KB Output is correct
8 Correct 311 ms 256816 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 258104 KB Output is correct
2 Correct 306 ms 256044 KB Output is correct
3 Correct 342 ms 254056 KB Output is correct
4 Correct 243 ms 252896 KB Output is correct
5 Correct 216 ms 252360 KB Output is correct
6 Correct 206 ms 252088 KB Output is correct
7 Correct 248 ms 256176 KB Output is correct
8 Correct 1 ms 704 KB Output is correct
9 Correct 4 ms 3668 KB Output is correct
10 Correct 349 ms 258188 KB Output is correct
11 Correct 360 ms 258140 KB Output is correct
12 Correct 366 ms 255340 KB Output is correct
13 Correct 313 ms 257996 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Correct 5 ms 3668 KB Output is correct
16 Correct 293 ms 257628 KB Output is correct
17 Correct 324 ms 257760 KB Output is correct
18 Correct 298 ms 257732 KB Output is correct
19 Correct 309 ms 257804 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 704 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 2 ms 708 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 5 ms 3668 KB Output is correct
14 Correct 5 ms 3756 KB Output is correct
15 Correct 3 ms 3720 KB Output is correct
16 Correct 5 ms 3668 KB Output is correct
17 Correct 4 ms 3668 KB Output is correct
18 Correct 7 ms 3796 KB Output is correct
19 Correct 4 ms 3528 KB Output is correct
20 Correct 5 ms 3668 KB Output is correct
21 Correct 4 ms 3668 KB Output is correct
22 Correct 5 ms 3756 KB Output is correct
23 Correct 5 ms 3668 KB Output is correct
24 Correct 6 ms 3732 KB Output is correct
25 Correct 185 ms 255392 KB Output is correct
26 Correct 204 ms 255360 KB Output is correct
27 Correct 205 ms 255556 KB Output is correct
28 Correct 180 ms 255164 KB Output is correct
29 Correct 271 ms 257352 KB Output is correct
30 Correct 213 ms 256612 KB Output is correct
31 Correct 287 ms 257660 KB Output is correct
32 Correct 223 ms 253056 KB Output is correct
33 Correct 224 ms 255648 KB Output is correct
34 Correct 252 ms 256664 KB Output is correct
35 Correct 228 ms 256644 KB Output is correct
36 Correct 227 ms 255316 KB Output is correct
37 Correct 340 ms 257356 KB Output is correct
38 Correct 250 ms 255996 KB Output is correct
39 Correct 328 ms 257760 KB Output is correct
40 Correct 307 ms 254744 KB Output is correct
41 Correct 298 ms 257164 KB Output is correct
42 Correct 329 ms 256764 KB Output is correct
43 Correct 311 ms 256816 KB Output is correct
44 Correct 358 ms 258104 KB Output is correct
45 Correct 306 ms 256044 KB Output is correct
46 Correct 342 ms 254056 KB Output is correct
47 Correct 243 ms 252896 KB Output is correct
48 Correct 216 ms 252360 KB Output is correct
49 Correct 206 ms 252088 KB Output is correct
50 Correct 248 ms 256176 KB Output is correct
51 Correct 1 ms 704 KB Output is correct
52 Correct 4 ms 3668 KB Output is correct
53 Correct 349 ms 258188 KB Output is correct
54 Correct 360 ms 258140 KB Output is correct
55 Correct 366 ms 255340 KB Output is correct
56 Correct 313 ms 257996 KB Output is correct
57 Correct 1 ms 724 KB Output is correct
58 Correct 5 ms 3668 KB Output is correct
59 Correct 293 ms 257628 KB Output is correct
60 Correct 324 ms 257760 KB Output is correct
61 Correct 298 ms 257732 KB Output is correct
62 Correct 309 ms 257804 KB Output is correct
63 Correct 260 ms 255484 KB Output is correct
64 Correct 275 ms 255788 KB Output is correct
65 Correct 268 ms 255532 KB Output is correct
66 Correct 342 ms 257264 KB Output is correct
67 Correct 338 ms 256732 KB Output is correct
68 Correct 337 ms 254580 KB Output is correct
69 Correct 324 ms 257268 KB Output is correct
70 Correct 311 ms 256840 KB Output is correct
71 Correct 348 ms 256952 KB Output is correct