#include <bits/stdc++.h>
using namespace std ;
const int MAX = 1e5 + 10 ;
int arr[MAX] ;
int n , k , m , q ;
pair<int , int>tree[20][4 * MAX] ;
pair<int , int>Merge(pair<int , int>&a , pair<int , int>&b)
{
return {min(a.first , b.first) , max(a.second , b.second)} ;
}
void update(int t , int node , int l , int r , int idx , pair<int , int>val)
{
if(idx > r || idx < l)
return ;
if(l == r)
{
tree[t][node] = val ;
return ;
}
int mid = (l + r) >> 1 ;
update(t , node << 1 , l , mid , idx , val) ;
update(t , node << 1 | 1 , mid+1 , r , idx , val) ;
tree[t][node] = Merge(tree[t][node << 1] , tree[t][node << 1 | 1]) ;
}
pair<int , int>query(int t , int node , int l , int r , int from , int to)
{
if(from > r || to < l || from > to)
return {1e9 , -1e9} ;
if(l >= from && r <= to)
return tree[t][node] ;
int mid = (l + r) >> 1 ;
pair<int , int>a = query(t , node << 1 , l , mid , from , to) ;
pair<int , int>b = query(t , node << 1 | 1 , mid+1 , r , from , to) ;
return Merge(a , b) ;
}
pair<int , int>to[MAX][20] ;
pair<int , int>old_to[MAX] ;
void preprocess()
{
multiset<int>sl , sr ;
for(int i = 1 ; i <= k-1 ; ++i)
sl.insert(to[i][0].first) ;
for(int i = 1 ; i <= n ; ++i)
{
old_to[i] = to[i][0] ;
sr.insert(to[i][0].second) ;
if(i+k-1 <= n)
sl.insert(to[i+k-1][0].first) ;
if(i-k >= 1)
sr.erase(sr.find(old_to[i-k].second)) ;
if(i > 1)
sl.erase(sl.find(old_to[i-1].first)) ;
to[i][0] = {*sl.begin() , *sr.rbegin()} ;
to[i][0].first = min(to[i][0].first , i) ;
to[i][0].second = max(to[i][0].second , i) ;
}
for(int i = 1 ; i <= n ; ++i)
update(0 , 1 , 1 , n , i , to[i][0]) ;
for(int j = 1 ; j < 20 ; ++j)
{
for(int i = 1 ; i <= n ; ++i)
{
to[i][j] = query(j-1 , 1 , 1 , n , to[i][j-1].first , to[i][j-1].second) ;
update(j , 1 , 1 , n , i , to[i][j]) ;
}
}
}
int solve(int x , int y)
{
if(y < to[x][19].first || y > to[x][19].second)
return -1 ;
int l = x , r = x , ans = 1 ;
for(int i = 19 ; i >= 0 ; --i)
{
pair<int , int>p = query(i , 1 , 1 , n , l , r) ;
if(y < p.first || y > p.second)
{
ans += (1 << i) ;
l = p.first , r = p.second ;
}
}
return ans ;
}
int main()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
cin>>n>>k ;
cin>>m ;
for(int i = 1 ; i <= n ; ++i)
to[i][0] = {1e9 , -1e9} ;
for(int i = 0 ; i < m ; ++i)
{
int l , r ;
cin>>l>>r ;
if(l > r)
to[l][0].first = min(to[l][0].first , r) ;
else
to[l][0].second = max(to[l][0].second , r) ;
}
preprocess() ;
cin>>q ;
while(q--)
{
int x , y ;
cin>>x>>y ;
cout<<solve(x , y)<<"\n" ;
}
return 0 ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
596 KB |
Output is correct |
2 |
Correct |
2 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
2 ms |
788 KB |
Output is correct |
5 |
Correct |
2 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
2 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
2 ms |
724 KB |
Output is correct |
10 |
Correct |
0 ms |
468 KB |
Output is correct |
11 |
Correct |
2 ms |
712 KB |
Output is correct |
12 |
Correct |
2 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
596 KB |
Output is correct |
2 |
Correct |
2 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
2 ms |
788 KB |
Output is correct |
5 |
Correct |
2 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
2 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
2 ms |
724 KB |
Output is correct |
10 |
Correct |
0 ms |
468 KB |
Output is correct |
11 |
Correct |
2 ms |
712 KB |
Output is correct |
12 |
Correct |
2 ms |
724 KB |
Output is correct |
13 |
Correct |
13 ms |
1504 KB |
Output is correct |
14 |
Correct |
13 ms |
1492 KB |
Output is correct |
15 |
Correct |
10 ms |
1444 KB |
Output is correct |
16 |
Correct |
8 ms |
1552 KB |
Output is correct |
17 |
Correct |
13 ms |
1412 KB |
Output is correct |
18 |
Correct |
9 ms |
1592 KB |
Output is correct |
19 |
Correct |
12 ms |
1496 KB |
Output is correct |
20 |
Correct |
9 ms |
1492 KB |
Output is correct |
21 |
Correct |
6 ms |
1484 KB |
Output is correct |
22 |
Correct |
12 ms |
1592 KB |
Output is correct |
23 |
Correct |
13 ms |
1500 KB |
Output is correct |
24 |
Correct |
13 ms |
1492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
756 ms |
58748 KB |
Output is correct |
2 |
Correct |
695 ms |
58704 KB |
Output is correct |
3 |
Correct |
726 ms |
58980 KB |
Output is correct |
4 |
Correct |
701 ms |
58688 KB |
Output is correct |
5 |
Correct |
450 ms |
64740 KB |
Output is correct |
6 |
Correct |
668 ms |
60216 KB |
Output is correct |
7 |
Correct |
426 ms |
64596 KB |
Output is correct |
8 |
Correct |
418 ms |
63012 KB |
Output is correct |
9 |
Correct |
428 ms |
63692 KB |
Output is correct |
10 |
Correct |
679 ms |
60188 KB |
Output is correct |
11 |
Correct |
624 ms |
64892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
803 ms |
64264 KB |
Output is correct |
2 |
Correct |
672 ms |
65584 KB |
Output is correct |
3 |
Correct |
1033 ms |
64420 KB |
Output is correct |
4 |
Correct |
562 ms |
65176 KB |
Output is correct |
5 |
Correct |
561 ms |
65288 KB |
Output is correct |
6 |
Correct |
601 ms |
65520 KB |
Output is correct |
7 |
Correct |
915 ms |
65480 KB |
Output is correct |
8 |
Correct |
832 ms |
65612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
690 ms |
62964 KB |
Output is correct |
2 |
Correct |
1148 ms |
59836 KB |
Output is correct |
3 |
Correct |
1030 ms |
59280 KB |
Output is correct |
4 |
Correct |
1034 ms |
58912 KB |
Output is correct |
5 |
Correct |
899 ms |
58668 KB |
Output is correct |
6 |
Correct |
952 ms |
58624 KB |
Output is correct |
7 |
Correct |
748 ms |
64440 KB |
Output is correct |
8 |
Correct |
2 ms |
724 KB |
Output is correct |
9 |
Correct |
12 ms |
1492 KB |
Output is correct |
10 |
Correct |
649 ms |
62472 KB |
Output is correct |
11 |
Correct |
742 ms |
65444 KB |
Output is correct |
12 |
Correct |
758 ms |
62384 KB |
Output is correct |
13 |
Correct |
784 ms |
65388 KB |
Output is correct |
14 |
Correct |
2 ms |
596 KB |
Output is correct |
15 |
Correct |
13 ms |
1492 KB |
Output is correct |
16 |
Correct |
729 ms |
60172 KB |
Output is correct |
17 |
Correct |
996 ms |
65620 KB |
Output is correct |
18 |
Correct |
945 ms |
60836 KB |
Output is correct |
19 |
Correct |
905 ms |
60896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
596 KB |
Output is correct |
2 |
Correct |
2 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
2 ms |
788 KB |
Output is correct |
5 |
Correct |
2 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
2 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
2 ms |
724 KB |
Output is correct |
10 |
Correct |
0 ms |
468 KB |
Output is correct |
11 |
Correct |
2 ms |
712 KB |
Output is correct |
12 |
Correct |
2 ms |
724 KB |
Output is correct |
13 |
Correct |
13 ms |
1504 KB |
Output is correct |
14 |
Correct |
13 ms |
1492 KB |
Output is correct |
15 |
Correct |
10 ms |
1444 KB |
Output is correct |
16 |
Correct |
8 ms |
1552 KB |
Output is correct |
17 |
Correct |
13 ms |
1412 KB |
Output is correct |
18 |
Correct |
9 ms |
1592 KB |
Output is correct |
19 |
Correct |
12 ms |
1496 KB |
Output is correct |
20 |
Correct |
9 ms |
1492 KB |
Output is correct |
21 |
Correct |
6 ms |
1484 KB |
Output is correct |
22 |
Correct |
12 ms |
1592 KB |
Output is correct |
23 |
Correct |
13 ms |
1500 KB |
Output is correct |
24 |
Correct |
13 ms |
1492 KB |
Output is correct |
25 |
Correct |
756 ms |
58748 KB |
Output is correct |
26 |
Correct |
695 ms |
58704 KB |
Output is correct |
27 |
Correct |
726 ms |
58980 KB |
Output is correct |
28 |
Correct |
701 ms |
58688 KB |
Output is correct |
29 |
Correct |
450 ms |
64740 KB |
Output is correct |
30 |
Correct |
668 ms |
60216 KB |
Output is correct |
31 |
Correct |
426 ms |
64596 KB |
Output is correct |
32 |
Correct |
418 ms |
63012 KB |
Output is correct |
33 |
Correct |
428 ms |
63692 KB |
Output is correct |
34 |
Correct |
679 ms |
60188 KB |
Output is correct |
35 |
Correct |
624 ms |
64892 KB |
Output is correct |
36 |
Correct |
803 ms |
64264 KB |
Output is correct |
37 |
Correct |
672 ms |
65584 KB |
Output is correct |
38 |
Correct |
1033 ms |
64420 KB |
Output is correct |
39 |
Correct |
562 ms |
65176 KB |
Output is correct |
40 |
Correct |
561 ms |
65288 KB |
Output is correct |
41 |
Correct |
601 ms |
65520 KB |
Output is correct |
42 |
Correct |
915 ms |
65480 KB |
Output is correct |
43 |
Correct |
832 ms |
65612 KB |
Output is correct |
44 |
Correct |
690 ms |
62964 KB |
Output is correct |
45 |
Correct |
1148 ms |
59836 KB |
Output is correct |
46 |
Correct |
1030 ms |
59280 KB |
Output is correct |
47 |
Correct |
1034 ms |
58912 KB |
Output is correct |
48 |
Correct |
899 ms |
58668 KB |
Output is correct |
49 |
Correct |
952 ms |
58624 KB |
Output is correct |
50 |
Correct |
748 ms |
64440 KB |
Output is correct |
51 |
Correct |
2 ms |
724 KB |
Output is correct |
52 |
Correct |
12 ms |
1492 KB |
Output is correct |
53 |
Correct |
649 ms |
62472 KB |
Output is correct |
54 |
Correct |
742 ms |
65444 KB |
Output is correct |
55 |
Correct |
758 ms |
62384 KB |
Output is correct |
56 |
Correct |
784 ms |
65388 KB |
Output is correct |
57 |
Correct |
2 ms |
596 KB |
Output is correct |
58 |
Correct |
13 ms |
1492 KB |
Output is correct |
59 |
Correct |
729 ms |
60172 KB |
Output is correct |
60 |
Correct |
996 ms |
65620 KB |
Output is correct |
61 |
Correct |
945 ms |
60836 KB |
Output is correct |
62 |
Correct |
905 ms |
60896 KB |
Output is correct |
63 |
Correct |
951 ms |
59640 KB |
Output is correct |
64 |
Correct |
1054 ms |
59748 KB |
Output is correct |
65 |
Correct |
943 ms |
59596 KB |
Output is correct |
66 |
Correct |
447 ms |
65636 KB |
Output is correct |
67 |
Correct |
901 ms |
60936 KB |
Output is correct |
68 |
Correct |
801 ms |
61248 KB |
Output is correct |
69 |
Correct |
635 ms |
65428 KB |
Output is correct |
70 |
Correct |
808 ms |
60900 KB |
Output is correct |
71 |
Correct |
973 ms |
60900 KB |
Output is correct |