oj.uz

Submission #894864

# Submission time Handle Problem Language Result Execution time Memory
894864 2023-12-29T06:34:32 Z juliany2 Railway Trip 2 (JOI22_ho_t4) C++17
35 / 100
 2000 ms 24248 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}; // or whatever ID
    inline T comb(T a, T b) { return max(a, b); } // 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 r[N], lift[N][L];
vector<int> e[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;

        int s = min(b, a + k - 1);
        e[a].push_back(b);
        e[s + 1].push_back(-b);
    }

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

    multiset<int> s;
    for (int i = 1; i <= n; i++) {
        for (int x : e[i]) {
            if (x > 0)
                s.insert(x);
            else
                s.erase(s.find(-x));
        }

        if (s.size())
            r[i] = *s.rbegin();

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

    for (int i = n; i >= 1; i--) {
        if (r[i])
            lift[i][0] = st.query(i, r[i])[1];
        else
            lift[i][0] = i;

        for (int j = 1; j < L; j++)
            lift[i][j] = lift[lift[i][j - 1]][j - 1];
    }

    int q;
    cin >> q;

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

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

        int ans = 1;
        for (int i = L - 1; ~i; i--) {
            if (r[lift[s][i]] < t)
                ans += (1 << i), s = lift[s][i];
        }
        s = lift[s][0];

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

    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2061 ms 4700 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2061 ms 4700 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2053 ms 9052 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 22528 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 19012 KB Output is correct
2 Correct 63 ms 17492 KB Output is correct
3 Correct 55 ms 15452 KB Output is correct
4 Correct 43 ms 14164 KB Output is correct
5 Correct 37 ms 13664 KB Output is correct
6 Correct 36 ms 13216 KB Output is correct
7 Correct 74 ms 22668 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 3 ms 6748 KB Output is correct
10 Correct 137 ms 22300 KB Output is correct
11 Correct 136 ms 24248 KB Output is correct
12 Correct 157 ms 22216 KB Output is correct
13 Correct 133 ms 24144 KB Output is correct
14 Correct 1 ms 4700 KB Output is correct
15 Correct 2 ms 4700 KB Output is correct
16 Correct 73 ms 19052 KB Output is correct
17 Correct 100 ms 19944 KB Output is correct
18 Correct 102 ms 19796 KB Output is correct
19 Correct 91 ms 19540 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2061 ms 4700 KB Time limit exceeded
2 Halted 0 ms 0 KB -