#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (200005)
ll N,Q, sum = 1;
ll parent[20][MAXN];
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
cin>>N;
pair<ll,ll> arr[N];
for(ll i = 0;i < N;i++){
cin>>arr[i].first>>arr[i].second;
}
set<pair<ll,ll> > s; //all ranges in the set do not intersect at any point in time so do not need to use multiset
ll Rptr = 0;
for(ll L = 0;L < N;L++){ //for each element L, the range where L can jump to with no extra cost (Rptr) is increasing monotonically
while(Rptr < N){
bool ok = 1;
auto it = s.lower_bound({arr[Rptr].first,-1e18});
if(!s.empty() && it != s.end()){
if(it->first <= arr[Rptr].second) ok = 0;
}
if(!s.empty() && it != s.begin()){ //remember that all ranges in the set do not intersect so (it--) [element with greatest L value] would have the greatest R value
it--;
if(it->second >= arr[Rptr].first) ok = 0;
}
if(ok){
s.insert(arr[Rptr]);
Rptr++;
}else{
break;
}
}
parent[0][L] = Rptr; //I can jump from L to Rptr with no cost ([L,Rptr - 1] can be in same lineup)
s.erase(s.find(arr[L]));
}
for(ll k = 0;k < 20;k++){ //since I set out-of-range as N, then i must make sure that my imaginary N pos is a stopper (self loop because there is no more position to jump towards on the right anymore)
parent[k][N] = N;
}
for(ll k = 1;k < 20;k++){
for(ll i = 0;i < N;i++){
parent[k][i] = parent[k-1][parent[k - 1][i]];
}
}
cin>>Q;
for(ll q = 0;q < Q;q++){
ll a,b;
cin>>a>>b;
a--, b--;
ll sum = 1; //number of lineups needed to jump from a to b
//note that this 2k-decomp is different from "ancestor" (instead of the usual way of jumping d distance, we need to jump to pos b (or less if its lineup start before pos b) which is unknown distance away
//we set parent[0][x] to be the nearest pos that cannot be in the same lineup as x (so the distance is all messed up already)
//then because we do not know the exact distance to jump but we can rely on the index to know if we will overjump or not (since we are jumping on an array)
for(ll k = 19;k >= 0;k--){
if(parent[k][a] <= b){
a = parent[k][a];
sum += (1ll<<k);
}
}
cout<<sum<<'\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
38352 KB |
Output is correct |
| 2 |
Correct |
49 ms |
38108 KB |
Output is correct |
| 3 |
Correct |
47 ms |
38224 KB |
Output is correct |
| 4 |
Correct |
51 ms |
38744 KB |
Output is correct |
| 5 |
Correct |
50 ms |
38636 KB |
Output is correct |
| 6 |
Correct |
43 ms |
37968 KB |
Output is correct |
| 7 |
Correct |
57 ms |
38480 KB |
Output is correct |
| 8 |
Correct |
47 ms |
37880 KB |
Output is correct |
| 9 |
Correct |
51 ms |
38224 KB |
Output is correct |
| 10 |
Correct |
54 ms |
37760 KB |
Output is correct |
| 11 |
Correct |
162 ms |
50120 KB |
Output is correct |
| 12 |
Correct |
146 ms |
48980 KB |
Output is correct |
| 13 |
Correct |
150 ms |
48932 KB |
Output is correct |
| 14 |
Correct |
138 ms |
44848 KB |
Output is correct |
| 15 |
Correct |
132 ms |
42996 KB |
Output is correct |
| 16 |
Correct |
6 ms |
31180 KB |
Output is correct |
| 17 |
Correct |
47 ms |
38484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
31320 KB |
Output is correct |
| 2 |
Correct |
7 ms |
31320 KB |
Output is correct |
| 3 |
Correct |
7 ms |
31320 KB |
Output is correct |
| 4 |
Correct |
7 ms |
31320 KB |
Output is correct |
| 5 |
Correct |
7 ms |
31320 KB |
Output is correct |
| 6 |
Correct |
7 ms |
31320 KB |
Output is correct |
| 7 |
Correct |
7 ms |
31320 KB |
Output is correct |
| 8 |
Correct |
7 ms |
31320 KB |
Output is correct |
| 9 |
Correct |
7 ms |
31424 KB |
Output is correct |
| 10 |
Correct |
7 ms |
31320 KB |
Output is correct |
| 11 |
Correct |
8 ms |
31576 KB |
Output is correct |
| 12 |
Correct |
8 ms |
31576 KB |
Output is correct |
| 13 |
Correct |
9 ms |
31760 KB |
Output is correct |
| 14 |
Correct |
8 ms |
31576 KB |
Output is correct |
| 15 |
Correct |
8 ms |
31576 KB |
Output is correct |
| 16 |
Correct |
6 ms |
31068 KB |
Output is correct |
| 17 |
Correct |
8 ms |
31320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
31320 KB |
Output is correct |
| 2 |
Correct |
7 ms |
31320 KB |
Output is correct |
| 3 |
Correct |
7 ms |
31320 KB |
Output is correct |
| 4 |
Correct |
7 ms |
31320 KB |
Output is correct |
| 5 |
Correct |
7 ms |
31320 KB |
Output is correct |
| 6 |
Correct |
7 ms |
31320 KB |
Output is correct |
| 7 |
Correct |
7 ms |
31320 KB |
Output is correct |
| 8 |
Correct |
7 ms |
31320 KB |
Output is correct |
| 9 |
Correct |
7 ms |
31424 KB |
Output is correct |
| 10 |
Correct |
7 ms |
31320 KB |
Output is correct |
| 11 |
Correct |
8 ms |
31576 KB |
Output is correct |
| 12 |
Correct |
8 ms |
31576 KB |
Output is correct |
| 13 |
Correct |
9 ms |
31760 KB |
Output is correct |
| 14 |
Correct |
8 ms |
31576 KB |
Output is correct |
| 15 |
Correct |
8 ms |
31576 KB |
Output is correct |
| 16 |
Correct |
6 ms |
31068 KB |
Output is correct |
| 17 |
Correct |
8 ms |
31320 KB |
Output is correct |
| 18 |
Correct |
62 ms |
34128 KB |
Output is correct |
| 19 |
Correct |
54 ms |
33884 KB |
Output is correct |
| 20 |
Correct |
60 ms |
34132 KB |
Output is correct |
| 21 |
Correct |
55 ms |
33872 KB |
Output is correct |
| 22 |
Correct |
60 ms |
33872 KB |
Output is correct |
| 23 |
Correct |
56 ms |
33864 KB |
Output is correct |
| 24 |
Correct |
64 ms |
33852 KB |
Output is correct |
| 25 |
Correct |
58 ms |
34032 KB |
Output is correct |
| 26 |
Correct |
58 ms |
33872 KB |
Output is correct |
| 27 |
Correct |
53 ms |
33684 KB |
Output is correct |
| 28 |
Correct |
42 ms |
33616 KB |
Output is correct |
| 29 |
Correct |
43 ms |
33872 KB |
Output is correct |
| 30 |
Correct |
45 ms |
33872 KB |
Output is correct |
| 31 |
Correct |
46 ms |
33616 KB |
Output is correct |
| 32 |
Correct |
43 ms |
33904 KB |
Output is correct |
| 33 |
Correct |
5 ms |
31064 KB |
Output is correct |
| 34 |
Correct |
47 ms |
33852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
38480 KB |
Output is correct |
| 2 |
Correct |
50 ms |
38336 KB |
Output is correct |
| 3 |
Correct |
45 ms |
37968 KB |
Output is correct |
| 4 |
Correct |
46 ms |
37712 KB |
Output is correct |
| 5 |
Correct |
47 ms |
37968 KB |
Output is correct |
| 6 |
Correct |
45 ms |
37968 KB |
Output is correct |
| 7 |
Correct |
46 ms |
37968 KB |
Output is correct |
| 8 |
Correct |
48 ms |
37740 KB |
Output is correct |
| 9 |
Correct |
49 ms |
37972 KB |
Output is correct |
| 10 |
Correct |
55 ms |
38480 KB |
Output is correct |
| 11 |
Correct |
141 ms |
48808 KB |
Output is correct |
| 12 |
Correct |
178 ms |
50640 KB |
Output is correct |
| 13 |
Correct |
146 ms |
48804 KB |
Output is correct |
| 14 |
Correct |
132 ms |
43344 KB |
Output is correct |
| 15 |
Correct |
143 ms |
44880 KB |
Output is correct |
| 16 |
Correct |
5 ms |
31064 KB |
Output is correct |
| 17 |
Correct |
44 ms |
37968 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
38352 KB |
Output is correct |
| 2 |
Correct |
49 ms |
38108 KB |
Output is correct |
| 3 |
Correct |
47 ms |
38224 KB |
Output is correct |
| 4 |
Correct |
51 ms |
38744 KB |
Output is correct |
| 5 |
Correct |
50 ms |
38636 KB |
Output is correct |
| 6 |
Correct |
43 ms |
37968 KB |
Output is correct |
| 7 |
Correct |
57 ms |
38480 KB |
Output is correct |
| 8 |
Correct |
47 ms |
37880 KB |
Output is correct |
| 9 |
Correct |
51 ms |
38224 KB |
Output is correct |
| 10 |
Correct |
54 ms |
37760 KB |
Output is correct |
| 11 |
Correct |
162 ms |
50120 KB |
Output is correct |
| 12 |
Correct |
146 ms |
48980 KB |
Output is correct |
| 13 |
Correct |
150 ms |
48932 KB |
Output is correct |
| 14 |
Correct |
138 ms |
44848 KB |
Output is correct |
| 15 |
Correct |
132 ms |
42996 KB |
Output is correct |
| 16 |
Correct |
6 ms |
31180 KB |
Output is correct |
| 17 |
Correct |
47 ms |
38484 KB |
Output is correct |
| 18 |
Correct |
7 ms |
31320 KB |
Output is correct |
| 19 |
Correct |
7 ms |
31320 KB |
Output is correct |
| 20 |
Correct |
7 ms |
31320 KB |
Output is correct |
| 21 |
Correct |
7 ms |
31320 KB |
Output is correct |
| 22 |
Correct |
7 ms |
31320 KB |
Output is correct |
| 23 |
Correct |
7 ms |
31320 KB |
Output is correct |
| 24 |
Correct |
7 ms |
31320 KB |
Output is correct |
| 25 |
Correct |
7 ms |
31320 KB |
Output is correct |
| 26 |
Correct |
7 ms |
31424 KB |
Output is correct |
| 27 |
Correct |
7 ms |
31320 KB |
Output is correct |
| 28 |
Correct |
8 ms |
31576 KB |
Output is correct |
| 29 |
Correct |
8 ms |
31576 KB |
Output is correct |
| 30 |
Correct |
9 ms |
31760 KB |
Output is correct |
| 31 |
Correct |
8 ms |
31576 KB |
Output is correct |
| 32 |
Correct |
8 ms |
31576 KB |
Output is correct |
| 33 |
Correct |
6 ms |
31068 KB |
Output is correct |
| 34 |
Correct |
8 ms |
31320 KB |
Output is correct |
| 35 |
Correct |
62 ms |
34128 KB |
Output is correct |
| 36 |
Correct |
54 ms |
33884 KB |
Output is correct |
| 37 |
Correct |
60 ms |
34132 KB |
Output is correct |
| 38 |
Correct |
55 ms |
33872 KB |
Output is correct |
| 39 |
Correct |
60 ms |
33872 KB |
Output is correct |
| 40 |
Correct |
56 ms |
33864 KB |
Output is correct |
| 41 |
Correct |
64 ms |
33852 KB |
Output is correct |
| 42 |
Correct |
58 ms |
34032 KB |
Output is correct |
| 43 |
Correct |
58 ms |
33872 KB |
Output is correct |
| 44 |
Correct |
53 ms |
33684 KB |
Output is correct |
| 45 |
Correct |
42 ms |
33616 KB |
Output is correct |
| 46 |
Correct |
43 ms |
33872 KB |
Output is correct |
| 47 |
Correct |
45 ms |
33872 KB |
Output is correct |
| 48 |
Correct |
46 ms |
33616 KB |
Output is correct |
| 49 |
Correct |
43 ms |
33904 KB |
Output is correct |
| 50 |
Correct |
5 ms |
31064 KB |
Output is correct |
| 51 |
Correct |
47 ms |
33852 KB |
Output is correct |
| 52 |
Correct |
55 ms |
38480 KB |
Output is correct |
| 53 |
Correct |
50 ms |
38336 KB |
Output is correct |
| 54 |
Correct |
45 ms |
37968 KB |
Output is correct |
| 55 |
Correct |
46 ms |
37712 KB |
Output is correct |
| 56 |
Correct |
47 ms |
37968 KB |
Output is correct |
| 57 |
Correct |
45 ms |
37968 KB |
Output is correct |
| 58 |
Correct |
46 ms |
37968 KB |
Output is correct |
| 59 |
Correct |
48 ms |
37740 KB |
Output is correct |
| 60 |
Correct |
49 ms |
37972 KB |
Output is correct |
| 61 |
Correct |
55 ms |
38480 KB |
Output is correct |
| 62 |
Correct |
141 ms |
48808 KB |
Output is correct |
| 63 |
Correct |
178 ms |
50640 KB |
Output is correct |
| 64 |
Correct |
146 ms |
48804 KB |
Output is correct |
| 65 |
Correct |
132 ms |
43344 KB |
Output is correct |
| 66 |
Correct |
143 ms |
44880 KB |
Output is correct |
| 67 |
Correct |
5 ms |
31064 KB |
Output is correct |
| 68 |
Correct |
44 ms |
37968 KB |
Output is correct |
| 69 |
Correct |
316 ms |
41608 KB |
Output is correct |
| 70 |
Correct |
323 ms |
42064 KB |
Output is correct |
| 71 |
Correct |
326 ms |
41292 KB |
Output is correct |
| 72 |
Correct |
310 ms |
41692 KB |
Output is correct |
| 73 |
Correct |
344 ms |
41808 KB |
Output is correct |
| 74 |
Correct |
369 ms |
42156 KB |
Output is correct |
| 75 |
Correct |
338 ms |
41596 KB |
Output is correct |
| 76 |
Correct |
327 ms |
42208 KB |
Output is correct |
| 77 |
Correct |
300 ms |
41208 KB |
Output is correct |
| 78 |
Correct |
324 ms |
41516 KB |
Output is correct |
| 79 |
Correct |
264 ms |
53328 KB |
Output is correct |
| 80 |
Correct |
233 ms |
51636 KB |
Output is correct |
| 81 |
Correct |
237 ms |
51536 KB |
Output is correct |
| 82 |
Correct |
226 ms |
46160 KB |
Output is correct |
| 83 |
Correct |
224 ms |
45484 KB |
Output is correct |
| 84 |
Correct |
5 ms |
31068 KB |
Output is correct |
| 85 |
Correct |
95 ms |
41328 KB |
Output is correct |
