#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
const int INF = 1e9;
int N, M, K;
pii A[MAXN+10];
pii operator + (const pii &p, const pii &q) { return {min(p.first, q.first), max(p.second, q.second)}; }
struct SEG
{
pii tree[MAXN*4+10];
void init(int node, int tl, int tr)
{
if(tl==tr)
{
tree[node]={tl, tl};
return;
}
int mid=tl+tr>>1;
init(node*2, tl, mid);
init(node*2+1, mid+1, tr);
tree[node]={INF, -INF};
}
void update(int node, int tl, int tr, int l, int r, pii k)
{
if(r<tl || tr<l) return;
if(l<=tl && tr<=r)
{
tree[node]=tree[node]+k;
return;
}
int mid=tl+tr>>1;
update(node*2, tl, mid, l, r, k);
update(node*2+1, mid+1, tr, l, r, k);
}
void query(int node, int tl, int tr, pii t)
{
t.first=min(t.first, tree[node].first);
t.second=max(t.second, tree[node].second);
if(tl==tr)
{
A[tl]=t;
return;
}
int mid=tl+tr>>1;
query(node*2, tl, mid, t);
query(node*2+1, mid+1, tr, t);
}
}seg;
struct SEG2
{
pii tree[MAXN*4+10][30];
pii query(int node, int tl, int tr, int l, int r, int k)
{
if(l<=tl && tr<=r) return tree[node][k];
if(r<tl || tr<l) return {INF, -INF};
int mid=tl+tr>>1;
return query(node*2, tl, mid, l, r, k)+query(node*2+1, mid+1, tr, l, r, k);
}
void flush(int node, int tl, int tr, int k)
{
if(tl==tr)
{
tree[node][k]=A[tl];
return;
}
int mid=tl+tr>>1;
flush(node*2, tl, mid, k);
flush(node*2+1, mid+1, tr, k);
tree[node][k]=tree[node*2][k]+tree[node*2+1][k];
}
void init()
{
flush(1, 1, N, 0);
for(int i=1; i<=20; i++)
{
for(int j=1; j<=N; j++) A[j]=query(1, 1, N, A[j].first, A[j].second, i-1);
flush(1, 1, N, i);
}
}
}seg2;
int main()
{
scanf("%d%d%d", &N, &K, &M);
seg.init(1, 1, N);
for(int i=1; i<=M; i++)
{
int l, r;
scanf("%d%d", &l, &r);
if(l<r)
{
seg.update(1, 1, N, l, min(l+K-1, r-1), {INF, r});
}
else
{
seg.update(1, 1, N, max(l-K+1, r+1), l, {r, -INF});
}
}
seg.query(1, 1, N, {INF, -INF});
seg2.init();
scanf("%d", &M);
while(M--)
{
int s, e;
scanf("%d%d", &s, &e);
pii t=seg2.query(1, 1, N, s, s, 20);
if(t.first>e || t.second<e) { printf("-1\n"); continue; }
int ans=0, l=s, r=s;
for(int i=19; i>=0; i--)
{
pii t=seg2.query(1, 1, N, l, r, i);
if(t.first>e || t.second<e)
{
ans|=(1<<i);
l=t.first; r=t.second;
}
}
printf("%d\n", ans+1);
}
}
Compilation message
Main.cpp: In member function 'void SEG::init(int, int, int)':
Main.cpp:27:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
27 | int mid=tl+tr>>1;
| ~~^~~
Main.cpp: In member function 'void SEG::update(int, int, int, int, int, pii)':
Main.cpp:41:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
41 | int mid=tl+tr>>1;
| ~~^~~
Main.cpp: In member function 'void SEG::query(int, int, int, pii)':
Main.cpp:55:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
55 | int mid=tl+tr>>1;
| ~~^~~
Main.cpp: In member function 'pii SEG2::query(int, int, int, int, int, int)':
Main.cpp:69:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
69 | int mid=tl+tr>>1;
| ~~^~~
Main.cpp: In member function 'void SEG2::flush(int, int, int, int)':
Main.cpp:80:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
80 | int mid=tl+tr>>1;
| ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:99:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | scanf("%d%d%d", &N, &K, &M);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
104 | scanf("%d%d", &l, &r);
| ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:117:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
117 | scanf("%d", &M);
| ~~~~~^~~~~~~~~~
Main.cpp:121:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
121 | scanf("%d%d", &s, &e);
| ~~~~~^~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
460 KB |
Output is correct |
2 |
Correct |
2 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
548 KB |
Output is correct |
4 |
Correct |
1 ms |
552 KB |
Output is correct |
5 |
Correct |
2 ms |
552 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
460 KB |
Output is correct |
8 |
Correct |
1 ms |
552 KB |
Output is correct |
9 |
Correct |
2 ms |
460 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
12 |
Correct |
1 ms |
460 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
460 KB |
Output is correct |
2 |
Correct |
2 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
548 KB |
Output is correct |
4 |
Correct |
1 ms |
552 KB |
Output is correct |
5 |
Correct |
2 ms |
552 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
460 KB |
Output is correct |
8 |
Correct |
1 ms |
552 KB |
Output is correct |
9 |
Correct |
2 ms |
460 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
12 |
Correct |
1 ms |
460 KB |
Output is correct |
13 |
Correct |
9 ms |
1348 KB |
Output is correct |
14 |
Correct |
9 ms |
1324 KB |
Output is correct |
15 |
Correct |
5 ms |
1228 KB |
Output is correct |
16 |
Correct |
4 ms |
1332 KB |
Output is correct |
17 |
Correct |
12 ms |
1336 KB |
Output is correct |
18 |
Correct |
7 ms |
1352 KB |
Output is correct |
19 |
Correct |
8 ms |
1356 KB |
Output is correct |
20 |
Correct |
5 ms |
1356 KB |
Output is correct |
21 |
Correct |
2 ms |
1228 KB |
Output is correct |
22 |
Correct |
7 ms |
1340 KB |
Output is correct |
23 |
Correct |
8 ms |
1356 KB |
Output is correct |
24 |
Correct |
9 ms |
1336 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
609 ms |
65608 KB |
Output is correct |
2 |
Correct |
551 ms |
65604 KB |
Output is correct |
3 |
Correct |
588 ms |
65764 KB |
Output is correct |
4 |
Correct |
549 ms |
65480 KB |
Output is correct |
5 |
Correct |
206 ms |
66916 KB |
Output is correct |
6 |
Correct |
586 ms |
67012 KB |
Output is correct |
7 |
Correct |
207 ms |
66624 KB |
Output is correct |
8 |
Correct |
154 ms |
65712 KB |
Output is correct |
9 |
Correct |
166 ms |
65664 KB |
Output is correct |
10 |
Correct |
429 ms |
66832 KB |
Output is correct |
11 |
Correct |
384 ms |
66884 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
567 ms |
66376 KB |
Output is correct |
2 |
Correct |
417 ms |
67524 KB |
Output is correct |
3 |
Correct |
838 ms |
66516 KB |
Output is correct |
4 |
Correct |
309 ms |
67060 KB |
Output is correct |
5 |
Correct |
321 ms |
67484 KB |
Output is correct |
6 |
Correct |
353 ms |
67460 KB |
Output is correct |
7 |
Correct |
666 ms |
67476 KB |
Output is correct |
8 |
Correct |
536 ms |
67648 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
520 ms |
67592 KB |
Output is correct |
2 |
Correct |
871 ms |
66568 KB |
Output is correct |
3 |
Correct |
796 ms |
65932 KB |
Output is correct |
4 |
Correct |
801 ms |
65688 KB |
Output is correct |
5 |
Correct |
679 ms |
65404 KB |
Output is correct |
6 |
Correct |
681 ms |
65128 KB |
Output is correct |
7 |
Correct |
521 ms |
64836 KB |
Output is correct |
8 |
Correct |
2 ms |
452 KB |
Output is correct |
9 |
Correct |
8 ms |
1356 KB |
Output is correct |
10 |
Correct |
475 ms |
64900 KB |
Output is correct |
11 |
Correct |
608 ms |
64828 KB |
Output is correct |
12 |
Correct |
604 ms |
65008 KB |
Output is correct |
13 |
Correct |
584 ms |
64972 KB |
Output is correct |
14 |
Correct |
2 ms |
460 KB |
Output is correct |
15 |
Correct |
10 ms |
1328 KB |
Output is correct |
16 |
Correct |
560 ms |
64752 KB |
Output is correct |
17 |
Correct |
772 ms |
65004 KB |
Output is correct |
18 |
Correct |
739 ms |
64848 KB |
Output is correct |
19 |
Correct |
726 ms |
64972 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
460 KB |
Output is correct |
2 |
Correct |
2 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
548 KB |
Output is correct |
4 |
Correct |
1 ms |
552 KB |
Output is correct |
5 |
Correct |
2 ms |
552 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
460 KB |
Output is correct |
8 |
Correct |
1 ms |
552 KB |
Output is correct |
9 |
Correct |
2 ms |
460 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
12 |
Correct |
1 ms |
460 KB |
Output is correct |
13 |
Correct |
9 ms |
1348 KB |
Output is correct |
14 |
Correct |
9 ms |
1324 KB |
Output is correct |
15 |
Correct |
5 ms |
1228 KB |
Output is correct |
16 |
Correct |
4 ms |
1332 KB |
Output is correct |
17 |
Correct |
12 ms |
1336 KB |
Output is correct |
18 |
Correct |
7 ms |
1352 KB |
Output is correct |
19 |
Correct |
8 ms |
1356 KB |
Output is correct |
20 |
Correct |
5 ms |
1356 KB |
Output is correct |
21 |
Correct |
2 ms |
1228 KB |
Output is correct |
22 |
Correct |
7 ms |
1340 KB |
Output is correct |
23 |
Correct |
8 ms |
1356 KB |
Output is correct |
24 |
Correct |
9 ms |
1336 KB |
Output is correct |
25 |
Correct |
609 ms |
65608 KB |
Output is correct |
26 |
Correct |
551 ms |
65604 KB |
Output is correct |
27 |
Correct |
588 ms |
65764 KB |
Output is correct |
28 |
Correct |
549 ms |
65480 KB |
Output is correct |
29 |
Correct |
206 ms |
66916 KB |
Output is correct |
30 |
Correct |
586 ms |
67012 KB |
Output is correct |
31 |
Correct |
207 ms |
66624 KB |
Output is correct |
32 |
Correct |
154 ms |
65712 KB |
Output is correct |
33 |
Correct |
166 ms |
65664 KB |
Output is correct |
34 |
Correct |
429 ms |
66832 KB |
Output is correct |
35 |
Correct |
384 ms |
66884 KB |
Output is correct |
36 |
Correct |
567 ms |
66376 KB |
Output is correct |
37 |
Correct |
417 ms |
67524 KB |
Output is correct |
38 |
Correct |
838 ms |
66516 KB |
Output is correct |
39 |
Correct |
309 ms |
67060 KB |
Output is correct |
40 |
Correct |
321 ms |
67484 KB |
Output is correct |
41 |
Correct |
353 ms |
67460 KB |
Output is correct |
42 |
Correct |
666 ms |
67476 KB |
Output is correct |
43 |
Correct |
536 ms |
67648 KB |
Output is correct |
44 |
Correct |
520 ms |
67592 KB |
Output is correct |
45 |
Correct |
871 ms |
66568 KB |
Output is correct |
46 |
Correct |
796 ms |
65932 KB |
Output is correct |
47 |
Correct |
801 ms |
65688 KB |
Output is correct |
48 |
Correct |
679 ms |
65404 KB |
Output is correct |
49 |
Correct |
681 ms |
65128 KB |
Output is correct |
50 |
Correct |
521 ms |
64836 KB |
Output is correct |
51 |
Correct |
2 ms |
452 KB |
Output is correct |
52 |
Correct |
8 ms |
1356 KB |
Output is correct |
53 |
Correct |
475 ms |
64900 KB |
Output is correct |
54 |
Correct |
608 ms |
64828 KB |
Output is correct |
55 |
Correct |
604 ms |
65008 KB |
Output is correct |
56 |
Correct |
584 ms |
64972 KB |
Output is correct |
57 |
Correct |
2 ms |
460 KB |
Output is correct |
58 |
Correct |
10 ms |
1328 KB |
Output is correct |
59 |
Correct |
560 ms |
64752 KB |
Output is correct |
60 |
Correct |
772 ms |
65004 KB |
Output is correct |
61 |
Correct |
739 ms |
64848 KB |
Output is correct |
62 |
Correct |
726 ms |
64972 KB |
Output is correct |
63 |
Correct |
768 ms |
64924 KB |
Output is correct |
64 |
Correct |
828 ms |
64944 KB |
Output is correct |
65 |
Correct |
753 ms |
64952 KB |
Output is correct |
66 |
Correct |
245 ms |
65252 KB |
Output is correct |
67 |
Correct |
769 ms |
65008 KB |
Output is correct |
68 |
Correct |
508 ms |
64832 KB |
Output is correct |
69 |
Correct |
326 ms |
64704 KB |
Output is correct |
70 |
Correct |
581 ms |
64876 KB |
Output is correct |
71 |
Correct |
652 ms |
65060 KB |
Output is correct |