[](http://cses.fi/problemset/task/1664/)664/

Firstly , we can see that the problem should use binary lifting with time complexity O(N+q*log(N)).

Surely at first many of you will confuse this problem by greedily following the movie, but that is the wrong way to solve it because it is trapping the order position according to array A.

So the correct solution to this problem is that we will be greedy according to the movie's running time, we will sort the ending time of each movie in ascending orderand combined with binary lifting.

In the worst case no more than 5e6 , we can totally do it this way.

Here is my sample solution

#include <bits/stdc++.h>
using namespace std;
const int N=1e6;
int p[20][N+5],nxt[N+5],en[N+5];
const int oo=N+1;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,q;
    cin >> n >> q;
    fill(en,en+N+2,oo);
    for(int i=1;i<=n;i++) {
        int a,b;
        cin >> a >> b;
        en[a]=min(en[a],b);
    }
    nxt[N+1]=oo;
    for(int i=N;i>=0;i--) {
        nxt[i]=min(nxt[i+1],en[i]);
    }
    for(int i=0;i<=N;i++) p[0][i]=nxt[i];
    for(int k=1;k<20;k++) {
        for(int i=0;i<=N;i++) {
            int mid=p[k-1][i];
            p[k][i]=(mid<=N?p[k-1][mid]:oo);
        }
    }
    while(q--) {
        int l,r;
        cin >> l >> r;
        int ans=0,pos=l;
        for(int k=19;~k,2025-05-14;k--) {
            int nx=p[k][pos];
            if(nx<=r) {
                ans+=(1<<k);
                pos=nx;
            }
        }
        cout << ans << '\n';
    }
}