#include <bits/stdc++.h>
using namespace std;
int n,k,m,q;
int a[200005],b[200005];
pair<int,int> v[20][100005];///intervalul in care pot ajunge din i facand 2^j pasi
int aintl[400005],aintr[400005];
int aintll[20][400005],aintrr[20][400005];
int lg[100005];
void build(int nod,int l,int r)
{
aintl[nod] = l;
aintr[nod] = r;
if (l != r)
{
int mij = (l + r) / 2;
build(2 * nod,l,mij);
build(2 * nod + 1,mij + 1,r);
}
}
void buildb(int nod,int l,int r,int b)
{
if (l == r)
{
aintl[nod] = v[b - 1][l].first;
aintr[nod] = v[b - 1][l].second;
}
else
{
int mij = (l + r) / 2;
buildb(2 * nod,l,mij,b);
buildb(2 * nod + 1,mij + 1,r,b);
aintl[nod] = min(aintl[2 * nod],aintl[2 * nod + 1]);
aintr[nod] = max(aintr[2 * nod],aintr[2 * nod + 1]);
}
}
void updater(int nod,int l,int r,int pos,int val)
{
if (l == r)
aintr[nod] = max(aintr[nod],val);
else
{
int mij = (l + r) / 2;
if (pos <= mij)
updater(2 * nod,l,mij,pos,val);
else
updater(2 * nod + 1,mij + 1,r,pos,val);
aintr[nod] = max(aintr[2 * nod],aintr[2 * nod + 1]);
}
}
void updatel(int nod,int l,int r,int pos,int val)
{
if (l == r)
aintl[nod] = min(aintl[nod],val);
else
{
int mij = (l + r) / 2;
if (pos <= mij)
updatel(2 * nod,l,mij,pos,val);
else
updatel(2 * nod + 1,mij + 1,r,pos,val);
aintl[nod] = min(aintl[2 * nod],aintl[2 * nod + 1]);
}
}
int queryr(int nod,int l,int r,int st,int dr)
{
if (r < st or dr < l)
return 0;
if (st <= l and r <= dr)
return aintr[nod];
int mij = (l + r) / 2;
return max(queryr(2 * nod,l,mij,st,dr),queryr(2 * nod + 1,mij + 1,r,st,dr));
}
int queryl(int nod,int l,int r,int st,int dr)
{
if (r < st or dr < l)
return n;
if (st <= l and r <= dr)
return aintl[nod];
int mij = (l + r) / 2;
return min(queryl(2 * nod,l,mij,st,dr),queryl(2 * nod + 1,mij + 1,r,st,dr));
}
void buildd(int nod,int l,int r,int b)
{
if (l == r)
{
aintll[b][nod] = v[b][l].first;
aintrr[b][nod] = v[b][l].second;
}
else
{
int mij = (l + r) / 2;
buildd(2 * nod,l,mij,b);
buildd(2 * nod + 1,mij + 1,r,b);
aintll[b][nod] = min(aintll[b][2 * nod],aintll[b][2 * nod + 1]);
aintrr[b][nod] = max(aintrr[b][2 * nod],aintrr[b][2 * nod + 1]);
}
}
int queryll(int nod,int l,int r,int st,int dr,int b)
{
if (r < st or dr < l)
return n;
if (st <= l and r <= dr)
return aintll[b][nod];
int mij = (l + r) / 2;
return min(queryll(2 * nod,l,mij,st,dr,b),queryll(2 * nod + 1,mij + 1,r,st,dr,b));
}
int queryrr(int nod,int l,int r,int st,int dr,int b)
{
if (r < st or dr < l)
return 0;
if (st <= l and r <= dr)
return aintrr[b][nod];
int mij = (l + r) / 2;
return max(queryrr(2 * nod,l,mij,st,dr,b),queryrr(2 * nod + 1,mij + 1,r,st,dr,b));
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> k >> m;
for (int i = 2; i <= n; i++)
lg[i] = 1 + lg[i / 2];
for (int i = 1; i <= m; i++)
cin >> a[i] >> b[i];
build(1,1,n);
for (int i = 1; i <= m; i++)
{
if (a[i] < b[i])
updater(1,1,n,a[i],b[i]);
else
updatel(1,1,n,a[i],b[i]);
}
for (int i = 1; i <= n; i++)
{
v[0][i].first = queryl(1,1,n,i,min(n,i + k - 1));
v[0][i].second = queryr(1,1,n,max(1,i - k + 1),i);
}
/*for (int i = 1; i <= n; i++)
cout << v[0][i].first << ' ' << v[0][i].second << '\n';;
cout << '\n';*/
for (int b = 1; b <= lg[n]; b++)
{
///v[b][i].first = min(v[b - 1][j].first), unde j in intervalul v[b - 1][i]
///v[b][i].second = max(v[b - 1][j].second), unde j in intervalul v[b - 1][i]
buildb(1,1,n,b);
for (int i = 1; i <= n; i++)
{
int intl = v[b - 1][i].first,intr = v[b - 1][i].second;
//out << intl << ' ' << intr << "->";
v[b][i].first = queryl(1,1,n,intl,intr);
v[b][i].second = queryr(1,1,n,intl,intr);
}
/*for (int i = 1; i <= n; i++)
cout << v[b][i].first << ' ' << v[b][i].second << '\n';;
cout << '\n';*/
}
for (int b = 0; b <= lg[n]; b++)
{
buildd(1,1,n,b);
//cout << "yup" << endl;
}
cin >> q;
for (int i = 1; i <= q; i++)
{
int s,f;
cin >> s >> f;
int intl = s,intr = s;
int cost = 0;
for (int jump = lg[n]; jump >= 0; jump--)
{
int newintl = queryll(1,1,n,intl,intr,jump);
int newintr = queryrr(1,1,n,intl,intr,jump);
if (f < newintl or f > newintr)
{
intl = newintl;
intr = newintr;
cost += (1 << jump);
}
}
if (f < queryll(1,1,n,intl,intr,0) or f > queryrr(1,1,n,intl,intr,0))
cout << -1 << '\n';
else
cout << cost + 1 << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
43352 KB |
Output is correct |
2 |
Correct |
8 ms |
43352 KB |
Output is correct |
3 |
Correct |
7 ms |
43352 KB |
Output is correct |
4 |
Correct |
7 ms |
43352 KB |
Output is correct |
5 |
Correct |
8 ms |
43352 KB |
Output is correct |
6 |
Correct |
7 ms |
43352 KB |
Output is correct |
7 |
Correct |
8 ms |
43352 KB |
Output is correct |
8 |
Correct |
7 ms |
43352 KB |
Output is correct |
9 |
Correct |
7 ms |
43352 KB |
Output is correct |
10 |
Correct |
2 ms |
14680 KB |
Output is correct |
11 |
Correct |
7 ms |
43352 KB |
Output is correct |
12 |
Correct |
8 ms |
43352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
43352 KB |
Output is correct |
2 |
Correct |
8 ms |
43352 KB |
Output is correct |
3 |
Correct |
7 ms |
43352 KB |
Output is correct |
4 |
Correct |
7 ms |
43352 KB |
Output is correct |
5 |
Correct |
8 ms |
43352 KB |
Output is correct |
6 |
Correct |
7 ms |
43352 KB |
Output is correct |
7 |
Correct |
8 ms |
43352 KB |
Output is correct |
8 |
Correct |
7 ms |
43352 KB |
Output is correct |
9 |
Correct |
7 ms |
43352 KB |
Output is correct |
10 |
Correct |
2 ms |
14680 KB |
Output is correct |
11 |
Correct |
7 ms |
43352 KB |
Output is correct |
12 |
Correct |
8 ms |
43352 KB |
Output is correct |
13 |
Correct |
20 ms |
47704 KB |
Output is correct |
14 |
Correct |
20 ms |
47440 KB |
Output is correct |
15 |
Correct |
13 ms |
47452 KB |
Output is correct |
16 |
Correct |
12 ms |
47704 KB |
Output is correct |
17 |
Correct |
17 ms |
47704 KB |
Output is correct |
18 |
Correct |
12 ms |
47704 KB |
Output is correct |
19 |
Correct |
13 ms |
47704 KB |
Output is correct |
20 |
Correct |
12 ms |
47704 KB |
Output is correct |
21 |
Correct |
9 ms |
47448 KB |
Output is correct |
22 |
Correct |
15 ms |
47704 KB |
Output is correct |
23 |
Correct |
16 ms |
47640 KB |
Output is correct |
24 |
Correct |
16 ms |
47704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
671 ms |
77904 KB |
Output is correct |
2 |
Correct |
644 ms |
78156 KB |
Output is correct |
3 |
Correct |
718 ms |
77928 KB |
Output is correct |
4 |
Correct |
618 ms |
77664 KB |
Output is correct |
5 |
Correct |
156 ms |
80176 KB |
Output is correct |
6 |
Correct |
624 ms |
79852 KB |
Output is correct |
7 |
Correct |
112 ms |
79556 KB |
Output is correct |
8 |
Correct |
104 ms |
77904 KB |
Output is correct |
9 |
Correct |
96 ms |
77904 KB |
Output is correct |
10 |
Correct |
515 ms |
79956 KB |
Output is correct |
11 |
Correct |
465 ms |
79952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
791 ms |
78420 KB |
Output is correct |
2 |
Correct |
578 ms |
80580 KB |
Output is correct |
3 |
Correct |
1073 ms |
79184 KB |
Output is correct |
4 |
Correct |
337 ms |
80252 KB |
Output is correct |
5 |
Correct |
310 ms |
80492 KB |
Output is correct |
6 |
Correct |
306 ms |
80464 KB |
Output is correct |
7 |
Correct |
875 ms |
80580 KB |
Output is correct |
8 |
Correct |
749 ms |
80588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
729 ms |
80780 KB |
Output is correct |
2 |
Correct |
1239 ms |
79136 KB |
Output is correct |
3 |
Correct |
1194 ms |
78012 KB |
Output is correct |
4 |
Correct |
1127 ms |
77652 KB |
Output is correct |
5 |
Correct |
909 ms |
77392 KB |
Output is correct |
6 |
Correct |
917 ms |
77672 KB |
Output is correct |
7 |
Correct |
602 ms |
78732 KB |
Output is correct |
8 |
Correct |
8 ms |
43352 KB |
Output is correct |
9 |
Correct |
14 ms |
47704 KB |
Output is correct |
10 |
Correct |
449 ms |
79952 KB |
Output is correct |
11 |
Correct |
599 ms |
80336 KB |
Output is correct |
12 |
Correct |
657 ms |
80344 KB |
Output is correct |
13 |
Correct |
627 ms |
80720 KB |
Output is correct |
14 |
Correct |
7 ms |
43352 KB |
Output is correct |
15 |
Correct |
18 ms |
47860 KB |
Output is correct |
16 |
Correct |
601 ms |
79960 KB |
Output is correct |
17 |
Correct |
1095 ms |
80712 KB |
Output is correct |
18 |
Correct |
1016 ms |
80628 KB |
Output is correct |
19 |
Correct |
931 ms |
80720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
43352 KB |
Output is correct |
2 |
Correct |
8 ms |
43352 KB |
Output is correct |
3 |
Correct |
7 ms |
43352 KB |
Output is correct |
4 |
Correct |
7 ms |
43352 KB |
Output is correct |
5 |
Correct |
8 ms |
43352 KB |
Output is correct |
6 |
Correct |
7 ms |
43352 KB |
Output is correct |
7 |
Correct |
8 ms |
43352 KB |
Output is correct |
8 |
Correct |
7 ms |
43352 KB |
Output is correct |
9 |
Correct |
7 ms |
43352 KB |
Output is correct |
10 |
Correct |
2 ms |
14680 KB |
Output is correct |
11 |
Correct |
7 ms |
43352 KB |
Output is correct |
12 |
Correct |
8 ms |
43352 KB |
Output is correct |
13 |
Correct |
20 ms |
47704 KB |
Output is correct |
14 |
Correct |
20 ms |
47440 KB |
Output is correct |
15 |
Correct |
13 ms |
47452 KB |
Output is correct |
16 |
Correct |
12 ms |
47704 KB |
Output is correct |
17 |
Correct |
17 ms |
47704 KB |
Output is correct |
18 |
Correct |
12 ms |
47704 KB |
Output is correct |
19 |
Correct |
13 ms |
47704 KB |
Output is correct |
20 |
Correct |
12 ms |
47704 KB |
Output is correct |
21 |
Correct |
9 ms |
47448 KB |
Output is correct |
22 |
Correct |
15 ms |
47704 KB |
Output is correct |
23 |
Correct |
16 ms |
47640 KB |
Output is correct |
24 |
Correct |
16 ms |
47704 KB |
Output is correct |
25 |
Correct |
671 ms |
77904 KB |
Output is correct |
26 |
Correct |
644 ms |
78156 KB |
Output is correct |
27 |
Correct |
718 ms |
77928 KB |
Output is correct |
28 |
Correct |
618 ms |
77664 KB |
Output is correct |
29 |
Correct |
156 ms |
80176 KB |
Output is correct |
30 |
Correct |
624 ms |
79852 KB |
Output is correct |
31 |
Correct |
112 ms |
79556 KB |
Output is correct |
32 |
Correct |
104 ms |
77904 KB |
Output is correct |
33 |
Correct |
96 ms |
77904 KB |
Output is correct |
34 |
Correct |
515 ms |
79956 KB |
Output is correct |
35 |
Correct |
465 ms |
79952 KB |
Output is correct |
36 |
Correct |
791 ms |
78420 KB |
Output is correct |
37 |
Correct |
578 ms |
80580 KB |
Output is correct |
38 |
Correct |
1073 ms |
79184 KB |
Output is correct |
39 |
Correct |
337 ms |
80252 KB |
Output is correct |
40 |
Correct |
310 ms |
80492 KB |
Output is correct |
41 |
Correct |
306 ms |
80464 KB |
Output is correct |
42 |
Correct |
875 ms |
80580 KB |
Output is correct |
43 |
Correct |
749 ms |
80588 KB |
Output is correct |
44 |
Correct |
729 ms |
80780 KB |
Output is correct |
45 |
Correct |
1239 ms |
79136 KB |
Output is correct |
46 |
Correct |
1194 ms |
78012 KB |
Output is correct |
47 |
Correct |
1127 ms |
77652 KB |
Output is correct |
48 |
Correct |
909 ms |
77392 KB |
Output is correct |
49 |
Correct |
917 ms |
77672 KB |
Output is correct |
50 |
Correct |
602 ms |
78732 KB |
Output is correct |
51 |
Correct |
8 ms |
43352 KB |
Output is correct |
52 |
Correct |
14 ms |
47704 KB |
Output is correct |
53 |
Correct |
449 ms |
79952 KB |
Output is correct |
54 |
Correct |
599 ms |
80336 KB |
Output is correct |
55 |
Correct |
657 ms |
80344 KB |
Output is correct |
56 |
Correct |
627 ms |
80720 KB |
Output is correct |
57 |
Correct |
7 ms |
43352 KB |
Output is correct |
58 |
Correct |
18 ms |
47860 KB |
Output is correct |
59 |
Correct |
601 ms |
79960 KB |
Output is correct |
60 |
Correct |
1095 ms |
80712 KB |
Output is correct |
61 |
Correct |
1016 ms |
80628 KB |
Output is correct |
62 |
Correct |
931 ms |
80720 KB |
Output is correct |
63 |
Correct |
1040 ms |
78228 KB |
Output is correct |
64 |
Correct |
1179 ms |
78672 KB |
Output is correct |
65 |
Correct |
1107 ms |
78596 KB |
Output is correct |
66 |
Correct |
183 ms |
80688 KB |
Output is correct |
67 |
Correct |
1016 ms |
80620 KB |
Output is correct |
68 |
Correct |
637 ms |
80428 KB |
Output is correct |
69 |
Correct |
337 ms |
80604 KB |
Output is correct |
70 |
Correct |
905 ms |
80756 KB |
Output is correct |
71 |
Correct |
1020 ms |
80580 KB |
Output is correct |