Submission #794388

#	Time	Username	Problem	Language	Result	Execution time	Memory
794388		1bin	Railway Trip 2 (JOI22_ho_t4)	C++14	100 / 100	365 ms	54276 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1e5 + 5;
const int B = 1 << 17;
int n, m, k, q, s, t, a, b;
pair<int, int> seg[17][B * 2];
vector<int> v[2][NMAX];
multiset<int> ms;

pair<int, int> operator /(const pair<int, int>& a, const pair<int, int>& b){
    return {min(a.first, b.first), max(a.second, b.second)};
}

void pull(int t){
    for(int i = B - 1; i; i--) seg[t][i] = seg[t][i * 2] / seg[t][i * 2 + 1];
}

pair<int,int> qry(int t, int l, int r){
    l += B; r += B;
    pair<int, int> p = {n + 1, 0};
    while(l <= r){
        if(l & 1) p = p / seg[t][l++];
        if(!(r & 1)) p = p / seg[t][r--];
        l /= 2; r /= 2;
    }
    return p;
}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> k >> m;
    while(m--){
        cin >> a >> b;
        if(a < b){
            v[0][a].emplace_back(b);
            v[0][min(a + k, b)].emplace_back(-b);
        }
        else{
            v[1][a].emplace_back(b);
            v[1][max(a - k, b)].emplace_back(-b);
        }
    }

    for(int i = 0; i < 17; i++)
        for(int j = 1; j < B * 2; j++) seg[i][j] = {n + 1, 0};
    for(int t = 0; t < 2; t++){
        multiset<int> ms;
        if(!t){
            for(int i = 1; i <= n; i++){
                for(int& x : v[t][i]){
                    if(x > 0) ms.emplace(x);
                    else ms.erase(ms.find(-x));
                }
                seg[0][B + i].second = (ms.empty() ? i : *ms.rbegin());
            }
        }
        else{
            for(int i = n; i; i--){
                for(int& x : v[t][i]){
                    if(x > 0) ms.emplace(x);
                    else ms.erase(ms.find(-x));
                }
                seg[0][B + i].first = (ms.empty() ? i : *ms.begin());
            }
        }
    }
    pull(0);

    for(int i = 1; i < 17; i++){
        for(int j = 1; j <= n; j++)
            seg[i][B + j] = qry(i - 1, seg[i - 1][B + j].first, seg[i - 1][B + j].second);
        pull(i);
    }
    cin >> q;
    while(q--){
        cin >> s >> t;
        int l = s, r = s, cur = 0;
        for(int i = 16; i >= 0; i--){
            auto [mn, mx] = qry(i, l, r);
            if(t < mn || t > mx){
                cur += 1 << i;
                l = mn, r = mx;
            }
        }
        if(++cur == (1 << 17)) cout << "-1\n";
        else cout << cur << '\n';
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:84:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |             auto [mn, mx] = qry(i, l, r);
      |                  ^

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