Submission #1227923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227923		Double_Slash	Railway Trip 2 (JOI22_ho_t4)	C++20	100 / 100	529 ms	74972 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
using pint = pair<int, int>;
 
int n, k, m, a[200000], b[200000], q;
template<int N>
struct St {
    int st[N << 1];
 
    void update(int i, int v) {
        for (st[i += N] = v; i >>= 1;) st[i] = max(st[i << 1], st[i << 1 | 1]);
    }
 
    int query(int l, int r) {
        int ret = -1e9;
        for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ret = max(ret, st[l++]);
            if (r & 1) ret = max(ret, st[--r]);
        }
        return ret;
    }

    int operator[](int i) { return st[i + N]; }
};
St<200000> l[18], r[18];

int main() {
    cin >> n >> k >> m;
    vector<int> add[n], rem[n + 1];
    for (int i = m; i--;) {
        cin >> a[i] >> b[i];
        if (--a[i] >= --b[i]) continue;
        add[a[i]].emplace_back(b[i]);
        rem[min(a[i] + k, b[i])].emplace_back(b[i]);
    }
    multiset<int> s;
    vector<St<200000>> l(18), r(18);
    for (int i = 0; i < n; ++i) {
        for (int x: add[i]) s.emplace(x);
        for (int x: rem[i]) s.erase(s.find(x));
        r[0].update(i, s.empty() ? i : *s.rbegin());
        add[i].clear();
        rem[i].clear();
    }
    for (int i = m; i--;) {
        if (b[i] >= a[i]) continue;
        add[max(b[i], a[i] - k) + 1].emplace_back(b[i]);
        rem[a[i] + 1].emplace_back(b[i]);
    }
    s.clear();
    for (int i = 0; i < n; ++i) {
        for (int x: add[i]) s.emplace(x);
        for (int x: rem[i]) s.erase(s.find(x));
        l[0].update(i, -(s.empty() ? i : *s.begin()));
    }
    for (int k = 0; ++k < 18;) {
        for (int i = n; i--;) {
            l[k].update(i, l[k - 1].query(-l[k - 1][i], r[k - 1][i] + 1));
            r[k].update(i, r[k - 1].query(-l[k - 1][i], r[k - 1][i] + 1));
        }
    }
    cin >> q;
    while (q--) {
        int si, ti;
        cin >> si >> ti;
        si--, ti--;
        int ans = 0;
        for (int k = 18, l0 = si, r0 = si; k--;) {
            int l1 = -l[k].query(l0, r0 + 1);
            int r1 = r[k].query(l0, r0 + 1);
            if (ti < l1 or ti > r1) {
                l0 = l1;
                r0 = r1;
                ans += 1 << k;
            }
        }
        cout << (ans >= n ? -1 : ans + 1) << endl;
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13