Submission #574622

#	Time	Username	Problem	Language	Result	Execution time	Memory
574622		JovanB	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	724 ms	73904 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 200000;
const int LOG = 19;

int L[LOG+1][N+5], R[LOG+1][N+5];

struct Segment{
    int lv[4*N+5], rv[4*N+5];
    void init(int node, int l, int r, int t){
        if(l == r){
            lv[node] = L[t][l];
            rv[node] = R[t][l];
            return;
        }
        int mid = (l+r)/2;
        init(node*2, l, mid, t);
        init(node*2+1, mid+1, r, t);
        lv[node] = min(lv[node*2], lv[node*2+1]);
        rv[node] = max(rv[node*2], rv[node*2+1]);
    }
    pair <int, int> query(int node, int l, int r, int tl, int tr){
        if(tl > r || l > tr) return {N + 5, 0};
        if(tl <= l && r <= tr) return {lv[node], rv[node]};
        int mid = (l+r)/2;
        pair <int, int> a = query(node*2, l, mid, tl, tr);
        pair <int, int> b = query(node*2+1, mid+1, r, tl, tr);
        return {min(a.first, b.first), max(a.second, b.second)};
    }
} seg[LOG+1];

multiset <int> q;

vector <int> vec[N+5];

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

    int n, k, m;
    cin >> n >> k >> m;
    for(int i=1; i<=m; i++){
        int l, r;
        cin >> l >> r;
        if(l <= r){
            vec[l].push_back(r);
            vec[min(l + k, r)].push_back(-r);
        }
        else{
            swap(l, r);
            vec[max(r - k + 1, l + 1)].push_back(l);
            vec[r + 1].push_back(-l);
        }
    }
    for(int i=1; i<=n; i++){
        for(auto c : vec[i]){
            if(c < 0){
                q.erase(q.find(-c));
            }
            else{
                q.insert(c);
            }
        }
        if(q.empty()) L[0][i] = R[0][i] = i;
        else{
            L[0][i] = min(i, *q.begin());
            R[0][i] = max(i, *q.rbegin());
        }
    }
    seg[0].init(1, 1, n, 0);
    for(int j=1; j<=LOG; j++){
        for(int i=1; i<=n; i++){
            pair <int, int> g = seg[j-1].query(1, 1, n, L[j-1][i], R[j-1][i]);
            L[j][i] = g.first;
            R[j][i] = g.second;
        }
        seg[j].init(1, 1, n, j);
    }
    int qrs;
    cin >> qrs;
    while(qrs--){
        int s, t;
        cin >> s >> t;
        int x = 0;
        int sl = s, sr = s;
        for(int j=LOG; j>=0; j--){
            pair <int, int> h = seg[j].query(1, 1, n, sl, sr);
            if(h.first > t || h.second < t){
                x += (1 << j);
                sl = h.first;
                sr = h.second;
            }
        }
        pair <int, int> h = seg[0].query(1, 1, n, sl, sr);
        if(h.first <= t && t <= h.second) cout << x + 1 << "\n";
        else cout << "-1\n";
    }
    return 0;
}

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