#ifndef Local
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define lim 1000000
using namespace std;
const int mod=1000000007ll;
multiset<pair<int,int>>cur;
bool checky(pair<int,int>b){
if(!cur.size())return 1;
auto it=cur.lower_bound({b.first,0});
if(it!=cur.end()){
//cerr<<"bruh\n";
if(it->first<=b.second)return 0;
}
if(it==cur.begin()){
//cerr<<"bruh1\n";
return 1;
}
it--;
if(b.first<=it->second){
//cerr<<"bruh2\n";
return 0;
}
return 1;
}
void solve(){
int n;
cin>>n;
pair<int,int>a[n];
for(int i=0;i<n;i++){
cin>>a[i].first>>a[i].second;
}
int dp[n][20];
int j=0;
for(int i=0;i<n;i++){
while(j<n&&checky(a[j])){
cur.insert(a[j]);
j++;
}// cerr<<(j<n)<<" "<<checky(a[j])<<"\n";
dp[i][0]=j-1;
cur.erase(a[i]);
}
/*
for(int i=0;i<n;i++)cerr<<dp[i][0]<<" ";
cerr<<"\n";
*/
for(int i=1;i<20;i++){
for(int j=0;j<n;j++){
if(dp[j][i-1]!=-1&&dp[j][i-1]+1<n)dp[j][i]=dp[dp[j][i-1]+1][i-1];
else dp[j][i]=-1;
//cerr<<dp[j][i]<<" ";
}//cerr<<"\n";
}
int q;
cin>>q;
while(q--){
int x,y;
cin>>x>>y;
x--,y--;
int res=0;
for(int i=19;0<=i;i--){
if(y<x)break;
if(dp[x][i]!=-1&&dp[x][i]<=y){
res+=1<<i;
//cerr<<x<<" "<<i<<"\n";
x=dp[x][i]+1;
}//else cerr<<"failed "<<x<<" "<<i<<"\n";
}
if(x<=y)res++;
cout<<res<<"\n";
//cerr<<"sure for now\n";
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
#ifdef Local
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
int t=1;
//cin>>t;
while (t--)
{
solve();
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
85 ms |
36944 KB |
Output is correct |
2 |
Correct |
85 ms |
36436 KB |
Output is correct |
3 |
Correct |
85 ms |
36536 KB |
Output is correct |
4 |
Correct |
86 ms |
36828 KB |
Output is correct |
5 |
Correct |
89 ms |
38364 KB |
Output is correct |
6 |
Correct |
73 ms |
35156 KB |
Output is correct |
7 |
Correct |
80 ms |
35568 KB |
Output is correct |
8 |
Correct |
83 ms |
36040 KB |
Output is correct |
9 |
Correct |
84 ms |
36716 KB |
Output is correct |
10 |
Correct |
83 ms |
35408 KB |
Output is correct |
11 |
Correct |
193 ms |
49312 KB |
Output is correct |
12 |
Correct |
178 ms |
46384 KB |
Output is correct |
13 |
Correct |
186 ms |
46416 KB |
Output is correct |
14 |
Correct |
169 ms |
44192 KB |
Output is correct |
15 |
Correct |
171 ms |
41452 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
76 ms |
37496 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
1372 KB |
Output is correct |
2 |
Correct |
3 ms |
1372 KB |
Output is correct |
3 |
Correct |
3 ms |
1372 KB |
Output is correct |
4 |
Correct |
3 ms |
1372 KB |
Output is correct |
5 |
Correct |
3 ms |
1372 KB |
Output is correct |
6 |
Correct |
4 ms |
1368 KB |
Output is correct |
7 |
Correct |
3 ms |
1372 KB |
Output is correct |
8 |
Correct |
3 ms |
1372 KB |
Output is correct |
9 |
Correct |
3 ms |
1236 KB |
Output is correct |
10 |
Correct |
3 ms |
1372 KB |
Output is correct |
11 |
Correct |
4 ms |
1628 KB |
Output is correct |
12 |
Correct |
4 ms |
1628 KB |
Output is correct |
13 |
Correct |
4 ms |
1668 KB |
Output is correct |
14 |
Correct |
4 ms |
1372 KB |
Output is correct |
15 |
Correct |
4 ms |
1372 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
3 ms |
1236 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
1372 KB |
Output is correct |
2 |
Correct |
3 ms |
1372 KB |
Output is correct |
3 |
Correct |
3 ms |
1372 KB |
Output is correct |
4 |
Correct |
3 ms |
1372 KB |
Output is correct |
5 |
Correct |
3 ms |
1372 KB |
Output is correct |
6 |
Correct |
4 ms |
1368 KB |
Output is correct |
7 |
Correct |
3 ms |
1372 KB |
Output is correct |
8 |
Correct |
3 ms |
1372 KB |
Output is correct |
9 |
Correct |
3 ms |
1236 KB |
Output is correct |
10 |
Correct |
3 ms |
1372 KB |
Output is correct |
11 |
Correct |
4 ms |
1628 KB |
Output is correct |
12 |
Correct |
4 ms |
1628 KB |
Output is correct |
13 |
Correct |
4 ms |
1668 KB |
Output is correct |
14 |
Correct |
4 ms |
1372 KB |
Output is correct |
15 |
Correct |
4 ms |
1372 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
3 ms |
1236 KB |
Output is correct |
18 |
Correct |
57 ms |
3836 KB |
Output is correct |
19 |
Correct |
54 ms |
3668 KB |
Output is correct |
20 |
Correct |
61 ms |
4060 KB |
Output is correct |
21 |
Correct |
56 ms |
3820 KB |
Output is correct |
22 |
Correct |
55 ms |
3892 KB |
Output is correct |
23 |
Correct |
54 ms |
3756 KB |
Output is correct |
24 |
Correct |
55 ms |
4012 KB |
Output is correct |
25 |
Correct |
62 ms |
3900 KB |
Output is correct |
26 |
Correct |
54 ms |
3872 KB |
Output is correct |
27 |
Correct |
49 ms |
3736 KB |
Output is correct |
28 |
Correct |
38 ms |
3692 KB |
Output is correct |
29 |
Correct |
40 ms |
3664 KB |
Output is correct |
30 |
Correct |
48 ms |
3668 KB |
Output is correct |
31 |
Correct |
39 ms |
3412 KB |
Output is correct |
32 |
Correct |
39 ms |
3664 KB |
Output is correct |
33 |
Correct |
0 ms |
348 KB |
Output is correct |
34 |
Correct |
40 ms |
3688 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
90 ms |
38640 KB |
Output is correct |
2 |
Correct |
87 ms |
37912 KB |
Output is correct |
3 |
Correct |
79 ms |
35156 KB |
Output is correct |
4 |
Correct |
81 ms |
34896 KB |
Output is correct |
5 |
Correct |
83 ms |
35924 KB |
Output is correct |
6 |
Correct |
69 ms |
35408 KB |
Output is correct |
7 |
Correct |
76 ms |
35116 KB |
Output is correct |
8 |
Correct |
79 ms |
35148 KB |
Output is correct |
9 |
Correct |
82 ms |
35016 KB |
Output is correct |
10 |
Correct |
88 ms |
37864 KB |
Output is correct |
11 |
Correct |
176 ms |
45904 KB |
Output is correct |
12 |
Correct |
198 ms |
50628 KB |
Output is correct |
13 |
Correct |
173 ms |
46092 KB |
Output is correct |
14 |
Correct |
161 ms |
41476 KB |
Output is correct |
15 |
Correct |
176 ms |
44824 KB |
Output is correct |
16 |
Correct |
0 ms |
344 KB |
Output is correct |
17 |
Correct |
71 ms |
35936 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
85 ms |
36944 KB |
Output is correct |
2 |
Correct |
85 ms |
36436 KB |
Output is correct |
3 |
Correct |
85 ms |
36536 KB |
Output is correct |
4 |
Correct |
86 ms |
36828 KB |
Output is correct |
5 |
Correct |
89 ms |
38364 KB |
Output is correct |
6 |
Correct |
73 ms |
35156 KB |
Output is correct |
7 |
Correct |
80 ms |
35568 KB |
Output is correct |
8 |
Correct |
83 ms |
36040 KB |
Output is correct |
9 |
Correct |
84 ms |
36716 KB |
Output is correct |
10 |
Correct |
83 ms |
35408 KB |
Output is correct |
11 |
Correct |
193 ms |
49312 KB |
Output is correct |
12 |
Correct |
178 ms |
46384 KB |
Output is correct |
13 |
Correct |
186 ms |
46416 KB |
Output is correct |
14 |
Correct |
169 ms |
44192 KB |
Output is correct |
15 |
Correct |
171 ms |
41452 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
76 ms |
37496 KB |
Output is correct |
18 |
Correct |
4 ms |
1372 KB |
Output is correct |
19 |
Correct |
3 ms |
1372 KB |
Output is correct |
20 |
Correct |
3 ms |
1372 KB |
Output is correct |
21 |
Correct |
3 ms |
1372 KB |
Output is correct |
22 |
Correct |
3 ms |
1372 KB |
Output is correct |
23 |
Correct |
4 ms |
1368 KB |
Output is correct |
24 |
Correct |
3 ms |
1372 KB |
Output is correct |
25 |
Correct |
3 ms |
1372 KB |
Output is correct |
26 |
Correct |
3 ms |
1236 KB |
Output is correct |
27 |
Correct |
3 ms |
1372 KB |
Output is correct |
28 |
Correct |
4 ms |
1628 KB |
Output is correct |
29 |
Correct |
4 ms |
1628 KB |
Output is correct |
30 |
Correct |
4 ms |
1668 KB |
Output is correct |
31 |
Correct |
4 ms |
1372 KB |
Output is correct |
32 |
Correct |
4 ms |
1372 KB |
Output is correct |
33 |
Correct |
0 ms |
348 KB |
Output is correct |
34 |
Correct |
3 ms |
1236 KB |
Output is correct |
35 |
Correct |
57 ms |
3836 KB |
Output is correct |
36 |
Correct |
54 ms |
3668 KB |
Output is correct |
37 |
Correct |
61 ms |
4060 KB |
Output is correct |
38 |
Correct |
56 ms |
3820 KB |
Output is correct |
39 |
Correct |
55 ms |
3892 KB |
Output is correct |
40 |
Correct |
54 ms |
3756 KB |
Output is correct |
41 |
Correct |
55 ms |
4012 KB |
Output is correct |
42 |
Correct |
62 ms |
3900 KB |
Output is correct |
43 |
Correct |
54 ms |
3872 KB |
Output is correct |
44 |
Correct |
49 ms |
3736 KB |
Output is correct |
45 |
Correct |
38 ms |
3692 KB |
Output is correct |
46 |
Correct |
40 ms |
3664 KB |
Output is correct |
47 |
Correct |
48 ms |
3668 KB |
Output is correct |
48 |
Correct |
39 ms |
3412 KB |
Output is correct |
49 |
Correct |
39 ms |
3664 KB |
Output is correct |
50 |
Correct |
0 ms |
348 KB |
Output is correct |
51 |
Correct |
40 ms |
3688 KB |
Output is correct |
52 |
Correct |
90 ms |
38640 KB |
Output is correct |
53 |
Correct |
87 ms |
37912 KB |
Output is correct |
54 |
Correct |
79 ms |
35156 KB |
Output is correct |
55 |
Correct |
81 ms |
34896 KB |
Output is correct |
56 |
Correct |
83 ms |
35924 KB |
Output is correct |
57 |
Correct |
69 ms |
35408 KB |
Output is correct |
58 |
Correct |
76 ms |
35116 KB |
Output is correct |
59 |
Correct |
79 ms |
35148 KB |
Output is correct |
60 |
Correct |
82 ms |
35016 KB |
Output is correct |
61 |
Correct |
88 ms |
37864 KB |
Output is correct |
62 |
Correct |
176 ms |
45904 KB |
Output is correct |
63 |
Correct |
198 ms |
50628 KB |
Output is correct |
64 |
Correct |
173 ms |
46092 KB |
Output is correct |
65 |
Correct |
161 ms |
41476 KB |
Output is correct |
66 |
Correct |
176 ms |
44824 KB |
Output is correct |
67 |
Correct |
0 ms |
344 KB |
Output is correct |
68 |
Correct |
71 ms |
35936 KB |
Output is correct |
69 |
Correct |
241 ms |
39496 KB |
Output is correct |
70 |
Correct |
270 ms |
41692 KB |
Output is correct |
71 |
Correct |
257 ms |
38780 KB |
Output is correct |
72 |
Correct |
245 ms |
40272 KB |
Output is correct |
73 |
Correct |
249 ms |
39708 KB |
Output is correct |
74 |
Correct |
253 ms |
41832 KB |
Output is correct |
75 |
Correct |
244 ms |
39108 KB |
Output is correct |
76 |
Correct |
253 ms |
41892 KB |
Output is correct |
77 |
Correct |
209 ms |
38732 KB |
Output is correct |
78 |
Correct |
240 ms |
39504 KB |
Output is correct |
79 |
Correct |
252 ms |
53084 KB |
Output is correct |
80 |
Correct |
231 ms |
49236 KB |
Output is correct |
81 |
Correct |
232 ms |
48724 KB |
Output is correct |
82 |
Correct |
217 ms |
45140 KB |
Output is correct |
83 |
Correct |
210 ms |
43228 KB |
Output is correct |
84 |
Correct |
0 ms |
348 KB |
Output is correct |
85 |
Correct |
124 ms |
38740 KB |
Output is correct |