A naive solution is to simulate the \(N\) contests one by one for each initial rating \(X\) given in a query. This approach costs \(O(NQ)\) time, which is not fast enough this time.

Here, instead of simulating the contests for each query, consider precalculating the answers for \(X=1,2,3,\ldots,5 \times 10^{5}\) before processing the queries, and respond the queries based on these precalculated values.

Unlike the original naive solution, we handle contests one by one, while updating the current rating originating from \(X=1,2,3,\ldots,5 \times 10^{5}\). Here, consider the following Dynamic Programming (DP):

\(dp[i][j]=(\)the rating after the \(i\) contest if the initial rating is \(j\)\()\). Initially, \(dp[0][j]=j\) for \(j=1,2,\ldots,5 \times 10^{5} \), and the transitions are as follows:

\(dp[i][j]=\left \{ \begin{array}{ll} dp_[i-1][j]+1 & (L_i \leq dp_{i-1,j} \leq R_i) \\ dp_[i-1][j] & (dp[i-1][j] <L_i \lor dp[i-1][j] >R_i) \end{array} \right\} \)

What we finally want is \(dp[N][*]\), but naively evaluating \(dp\) is not fast enough, so we will try to optimize it based on the property of this array.

One notable property is that \(dp[i][j] \leq dp[i][j+1]\) for all \(j\). Since the rating always changes by \(1\), while the rating starting from \(X\) and \(X+1\) can become the same, once they become the same they never diverge, thus the ordering between the initial ratings and those after any contest never flip.

In other words, in the DP transition above, we have a pair \(l\) and \(r\) such that, \(dp[i][j]=dp[i-1][j]+1\) for all \(l \leq j \leq r\), and \(dp[i][j]=dp[i-1][j]\) otherwise.

That is why we can process the DP in-place. Let us drop the index \(i\) in \(dp[i][j]\), and update \(D[j]\) sequentially. The operations required against \(D\) is retrieval of an element, and segment addition. Thus, \(dp[N]\) can be found using a lazy segment tree. An element retrieval on a segment tree costs \(O(\log X)\) time, and binary search costs \(O(\log X)\), which is performed for the \(N\) contests, so the problem can be solved in a total of \(O(X+N (\log X)^2 +Q \log X)\) time.

By making the lazy segment tree support both segment-max and segment-add, one can use the binary-searching trick on a segment tree when determining \(l\) and \(r\) (as in max_right and min_left in ACL (AtCoder Library)), which reduces the time complexity to \(O(X+N \log X+Q \log X)\). The sample code does adopt this trick.

Sample code (C++):

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

int op(int a, int b) { return max(a, b); }
int e() { return -1e9; }
int mapping(int f, int x) { return f + x; }
int composition(int f, int g) { return f + g; }
int id() { return 0; }

int main() {
    int n;
    cin >> n;
    vector<int> l(n), r(n);
    for (int i = 0; i < n; ++i) {
        cin >> l[i] >> r[i];
    }
    vector<int> rate(500000, 0);
    iota(rate.begin(), rate.end(), 1);
    atcoder::lazy_segtree<int, op, e, int, mapping, composition, id> seg(rate);
    for (int i = 0; i < n; ++i) {
        auto L = seg.max_right(0, [&](int x) { return x < l[i]; });
        auto R = seg.max_right(0, [&](int x) { return x <= r[i]; });
        seg.apply(L, R, 1);
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int x;
        cin >> x;
        x--;
        cout << seg.get(x) << "\n";
    }
}