Submission #75559300

---

Source Code Expand

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,m,q;
    cin >> n >> m >> q;
    vector<int>nxt(n+5,n+2);
    for(int i = 1; i<=m; i++){
        int a,b;
        cin >> a >> b;
        b++;
        nxt[a] = min(nxt[a],b);
    }
    for(int i = n+3; i>=1; i--){
        nxt[i] = min(nxt[i+1],nxt[i]);
    }
    const int ln = 20;
    vector<vector<int>>dp(n+5,vector<int>(ln));
    for(int i = 1; i<=n+4; i++){
        dp[i][0] = nxt[i];
    }
    for(int j = 1; j<ln; j++){
        for(int i = 1; i<=n+4; i++){
            dp[i][j] = dp[dp[i][j-1]][j-1];
        }
    }
    while(q--){
        int l,r;
        cin >> l >> r;
        r++;
        int ans = 0;
        for(int j = ln-1; j>=0; j--){
            if(dp[l][j] <= r){
                ans += 1<<j;
                l = dp[l][j];
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

Submission Info

Judge Result