제출 #1326767

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326767		bbldrizzy	Railway Trip 2 (JOI22_ho_t4)	C++20	100 / 100	1156 ms	104828 KiB

Main

#include <bits/stdc++.h>
#include <ios>
#include <iostream>
#include <set>
#include <random>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define f first
#define s second
const ll MOD = 1e9+7;
const ll inf = 4*1e18;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

long long md(long long a, long long m) {
    return (a % m + m) % m;
}

template<typename T> struct SegTreeMax {
    int n;
    vector<T> st;
    T ID; // identity (very small for max)

    SegTreeMax(int _n = 0) { init(_n); }

    void init(int _n) {
        n = _n;
        ID = numeric_limits<T>::lowest();
        st.assign(4 * max(1, n), ID);
    }

    // build from array a (0-indexed)
    void build(const vector<T>& a) {
        if ((int)a.size() != n) { init((int)a.size()); n = a.size(); }
        build(1, 0, n - 1, a);
    }

    void build(int v, int tl, int tr, const vector<T>& a) {
        if (tl == tr) {
            st[v] = a[tl];
        } else {
            int tm = (tl + tr) / 2;
            build(2*v, tl, tm, a);
            build(2*v+1, tm+1, tr, a);
            st[v] = max(st[2*v], st[2*v+1]);
        }
    }

    // point update: set position pos to value val
    void update(int pos, T val) { update(1, 0, n - 1, pos, val); }
    void update(int v, int tl, int tr, int pos, T val) {
        if (tl == tr) {
            st[v] = val;
            return;
        }
        int tm = (tl + tr) / 2;
        if (pos <= tm) update(2*v, tl, tm, pos, val);
        else update(2*v+1, tm+1, tr, pos, val);
        st[v] = max(st[2*v], st[2*v+1]);
    }

    // range max query on [l, r] inclusive
    T query(int l, int r) { return query(1, 0, n - 1, l, r); }
    T query(int v, int tl, int tr, int l, int r) {
        if (l > r) return ID;
        if (l == tl && r == tr) return st[v];
        int tm = (tl + tr) / 2;
        return max(
            query(2*v, tl, tm, l, min(r, tm)),
            query(2*v+1, tm+1, tr, max(l, tm+1), r)
        );
    }
};

int main() {
    // freopen("input.in", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, k, m; cin >> n >> k >> m;
    vector<int> l(n, 0);
    vector<int> r(n, 0);
    multiset<pair<pair<int, int>, int>> st;
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b; --a; --b;
        if (a < b) {
            int en = min(a+k-1, b-1)+1;
            st.insert({{a, b}, 0});
            st.insert({{en, b}, 1});
        } else {
            int en = max(a-k+1, b+1)-1;
            st.insert({{a, b}, 2});
            st.insert({{en, b}, 3});
        }
    }
    multiset<int> st2;
    auto it = st.begin();
    for (int i = 0; i < n; i++) {
        while (it != st.end() && (*it).f.f == i) {
            if ((*it).s == 0) {
                st2.insert((*it).f.s); 
            } else if ((*it).s == 1) {
                st2.erase(st2.find((*it).f.s));
            }
            it++;
        }
        if (st2.empty()) r[i] = i;
        else {r[i] = *(st2.rbegin());}
    }
    auto it2 = st.rbegin();
    for (int i = n-1; i >= 0; i--) {
        while (it2 != st.rend() && (*it2).f.f == i) {
            if ((*it2).s == 2) {
                st2.insert((*it2).f.s); 
            } else if ((*it2).s == 3) {
                st2.erase(st2.find((*it2).f.s));
            }
            it2++;
        }
        if (st2.empty()) l[i] = i;
        else {l[i] = *(st2.begin());}
    }
    vector<vector<pair<int, int>>> lft(n, vector<pair<int, int>>(18));
    vector<int> l1(n, -1e9);
    vector<int> r1(n, 0);
    vector<pair<SegTreeMax<int>, SegTreeMax<int>>> lft2(18);
    for (int j = 0; j < 18; j++) {
        lft2[j].f.build(l1);
        lft2[j].s.build(r1);
    }
    SegTreeMax<int> sl; sl.build(l1); 
    SegTreeMax<int> sr; sr.build(r1);
    for (int i = 0; i < n; i++) {
        lft[i][0] = {(l[i] ==  -1e9) ? i : l[i], (r[i] == 1e9) ? i : r[i]};
        sl.update(i, -(lft[i][0].f));
        sr.update(i, lft[i][0].s);
    }
    lft2[0].f = sl;
    lft2[0].s = sr;
    for (int k = 1; k < 18; k++) {
        for (int j = 0; j < n; j++) {
            int L = lft[j][k-1].f; int R = lft[j][k-1].s;
            lft[j][k].f = -sl.query(L, R);
            lft[j][k].s = sr.query(L, R);
        }
        for (int j = 0; j < n; j++) {
            sl.update(j, -lft[j][k].f);
            sr.update(j, lft[j][k].s);
        }
        lft2[k].f = sl;
        lft2[k].s = sr;
    }
    int q; cin >> q;
    for (int i = 0; i < q; i++) {
        int x, y; cin >> x >> y; --x; --y;
        int str = x; int en = x;
        int sm = 0;
        for (int j = 17; j >= 0; j--) {
            assert(str <= en);
            int tstr = -(lft2[j].f).query(str, en);
            int ten = lft2[j].s.query(str, en);
            if (!(y >= tstr && y <= ten)) {
                sm += (1 << j);
                str = tstr; en = ten;
            }
        }
        str = -lft2[0].f.query(str, en);
        en = lft2[0].s.query(str, en);
        sm += 1;
        cout << ((y >= str && y <= en) ? sm : -1) << "\n";
    }
}   

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