Submission #865566

#	Time	Username	Problem	Language	Result	Execution time	Memory
865566		blackslex	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	856 ms	113796 KiB

Main

#include<bits/stdc++.h>

using namespace std;
using pii = pair<int,int>;

const int N = 1e5 + 5, M = 2e5 + 5, K = 20;
int n, m, k, q, x, y, mn[K][M], mx[K][M];
vector<pii> v;
vector<int> add[N], del[N];
multiset<int> msa;
multiset<int, greater<int>> msb;

struct segment {
    struct node {
        int mns, mxs;
        node() : mns(INT_MAX), mxs(INT_MIN) {}
        node(int mnval, int mxval) : mns(mnval), mxs(mxval) {}
        friend node operator + (node a, node b) {
            node res = node();
            res.mns = min(a.mns, b.mns);
            res.mxs = max(a.mxs, b.mxs);
            return res;
        }
    } t[N * 4];
    void build (int l, int r, int idx, int lf) {
        if (l == r) return void(t[idx] = node(mn[lf][l], mx[lf][l]));
        int mid = (l + r) >> 1;
        build(l, mid, idx * 2 + 1, lf);
        build(mid + 1, r, idx * 2 + 2, lf);
        t[idx] = t[idx * 2 + 1] + t[idx * 2 + 2];
    }
    node qr (int l, int r, int idx, int tl, int tr) {
        if (l > tr || r < tl) return node();
        if (l >= tl && r <= tr) return t[idx];
        int mid = (l + r) >> 1;
        return qr(l, mid, idx * 2 + 1, tl, tr) + qr(mid + 1, r, idx * 2 + 2, tl, tr);
    }
} segm[K];

void solve() {
    scanf("%d %d", &x, &y);
    if (mn[K - 1][x] > y || mx[K - 1][x] < y) return void(printf("-1\n"));
    int l = x, r = x, ans = 0;
    for (int i = K - 1; i >= 0; i--) {
        int mni = segm[i].qr(1, n, 0, l, r).mns;
        int mxi = segm[i].qr(1, n, 0, l, r).mxs;
        if (mni <= y && mxi >= y) continue;
        ans += (1 << i); l = mni; r = mxi;
    }
    printf("%d\n", ++ans);
}

int main() {
    scanf("%d %d %d", &n, &k, &m); v.resize(m);
    for (auto &[a, b]: v) scanf("%d %d", &a, &b);
    for (int i = 0; i < m; i++) {
        auto [a, b] = v[i];
        if (a < b) continue;
        add[max(a - k + 1, b)].emplace_back(i);
        del[a].emplace_back(i);
    }
    for (int i = 1; i <= n; i++) {
        for (auto &e: add[i]) msa.emplace(v[e].second);
        mn[0][i] = (msa.empty() ? i : *msa.begin());
        for (auto &e: del[i]) msa.erase(msa.find(v[e].second));
    }
    for (int i = 1; i <= n; i++) add[i].clear(), del[i].clear();
    for (int i = 0; i < m; i++) {
        auto [a, b] = v[i];
        if (a > b) continue;
        add[a].emplace_back(i);
        del[min(a + k - 1, b)].emplace_back(i);
    }
    for (int i = 1; i <= n; i++) {
        for (auto &e: add[i]) msb.emplace(v[e].second);
        mx[0][i] = (msb.empty() ? i : *msb.begin());
        for (auto &e: del[i]) msb.erase(msb.find(v[e].second));
    }
    segm[0].build(1, n, 0, 0);
    for (int i = 1; i < K; i++) {
        for (int j = 1; j <= n; j++) {
            mn[i][j] = segm[i - 1].qr(1, n, 0, mn[i - 1][j], mx[i - 1][j]).mns;
            mx[i][j] = segm[i - 1].qr(1, n, 0, mn[i - 1][j], mx[i - 1][j]).mxs;
        }
        segm[i].build(1, n, 0, i);
    }
    scanf("%d", &q);
    while (q--) solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     scanf("%d %d", &x, &y);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%d %d %d", &n, &k, &m); v.resize(m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:55:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     for (auto &[a, b]: v) scanf("%d %d", &a, &b);
      |                           ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~

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