Submission #1123843

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123843		Neco_arc	Railway Trip 2 (JOI22_ho_t4)	C++20	100 / 100	283 ms	30268 KiB

Main

#include <bits/stdc++.h>

#define ll long long
#define name "Railway Trip 2"
#define fi(i, a, b)  for(int i = a; i <= b; ++i)
#define fid(i, a, b) for(int i = a; i >= b; --i)
#define maxn (int) (1e5 + 7)

using namespace std;

int n, m, k;
pair<int, int> Range[maxn];

inline pair<int, int> cb(pair<int, int> x, pair<int, int> y) {
    return { min(x.first, y.first), max(x.second, y.second) };
}

struct IT {

    pair<int, int> st[2 * maxn];


    void update(int x, pair<int, int> val) {
        int id = x + n;
        st[id] = val;
        while(id != 1) {
            id >>= 1;
            st[id] = cb(st[id * 2], st[id * 2 + 1]);
        }
    }

    pair<int, int> get(int l, int r) {
        pair<int, int> ans = {n + 1, 0};
        l += n, r += n;

        while(l <= r) {
            ans = cb(ans, st[l]), ans = cb(ans, st[r]);
            l = (l + 1) >> 1, r = (r - 1) >> 1;
        }

        return ans;
    }

} St[18];

pair<int, int> dq[maxn];
void prepare() {
    int d = 1, c = 0;

    fi(i, 1, n) {
        while(d <= c && dq[c].first < Range[i].second) -- c;
        dq[++c] = {Range[i].second, i};
        while(d <= c && dq[d].second < i - k + 1) ++d;

        Range[i].second = dq[d].first;
    }

    d = 1, c = 0;
    fid(i, n, 1) {
        while(d <= c && dq[c].first > Range[i].first) --c;
        dq[++c] = {Range[i].first, i};
        while(d <= c && dq[d].second > i + k - 1) ++d;

        Range[i].first = dq[d].first;
    }


}

int query(int x, int y) {
    auto [l, r] = St[17].get(x, x);
    if(!(l <= y && y <= r)) return -1;

    int ans = 0; l = x, r = x;
    fid(i, 17, 0) {
        auto [u, v] = St[i].get(l, r);
        if(!(u <= y && y <= v)) l = u, r = v, ans += 1 << i;
    }

    return ans + 1;
}

void solve() {

    cin >> n >> k >> m;
    fi(i, 1, n) Range[i] = {i, i};

    fi(i, 1, m) {
        int x, y; cin >> x >> y;
        Range[x] = cb(Range[x], {y, y});
    }

    prepare();


    fi(i, 1, n) St[0].update(i, Range[i]);
    fi(j, 1, 17) {
        fi(i, 1, n) {
            auto [l, r] = St[j - 1].get(i, i);
            St[j].update(i, St[j - 1].get(l, r));
        }
    }

    int q; cin >> q;
    fi(i, 1, q) {
        int x, y; cin >> x >> y;
        cout << query(x, y) << '\n';
    }


}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    if(fopen(name".inp", "r")) {
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }

    solve();

}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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