#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(a,b) for (int a = 0; a < (b); ++a)
#define pb push_back
#define all(t) t.begin(), t.end()
const int MAXN = 2e5+5, base = (1<<18), rozmiar_drzewa = base * 2, INF = 1e9+50, LG = 17;
int n = 0, k = 0, m = 0, q = 0, a = 0, b = 0;
vector<int> tree_min;
vector<int> tree_max;
int A_min[LG+1][MAXN];
int A_max[LG+1][MAXN];
int tree_minn[LG+1][rozmiar_drzewa];
int tree_maxx[LG+1][rozmiar_drzewa];
inline void update_min(int l, int p, int val)
{
l = l + base - 1, p = p + base + 1;
while(l / 2 != p / 2)
{
if(l % 2 == 0) tree_min[l+1] = min(tree_min[l+1],val);
if(p % 2 == 1) tree_min[p-1] = min(tree_min[p-1],val);
l /= 2, p /= 2;
}
}
inline void update_max(int l, int p, int val)
{
l = l + base - 1, p = p + base + 1;
while(l / 2 != p / 2)
{
if(l % 2 == 0) tree_max[l+1] = max(tree_max[l+1],val);
if(p % 2 == 1) tree_max[p-1] = max(tree_max[p-1],val);
l /= 2, p /= 2;
}
}
inline int query_min(int v)
{
int res = INF;
v += base;
while(v > 0)
{
res = min(res,tree_min[v]);
v /= 2;
}
return res;
}
inline int query_max(int v)
{
int res = -INF;
v += base;
while(v > 0)
{
res = max(res,tree_max[v]);
v /= 2;
}
return res;
}
inline int query_min2(int l, int p, int idx)
{
l = l + base - 1, p = p + base + 1;
int res = INF;
while(l / 2 != p / 2)
{
if(l % 2 == 0) res = min(res,tree_minn[idx][l+1]);
if(p % 2 == 1) res = min(res,tree_minn[idx][p-1]);
l /= 2, p /= 2;
}
return res;
}
inline int query_max2(int l, int p, int idx)
{
l = l + base - 1, p = p + base + 1;
int res = -INF;
while(l / 2 != p / 2)
{
if(l % 2 == 0) res = max(res,tree_maxx[idx][l+1]);
if(p % 2 == 1) res = max(res,tree_maxx[idx][p-1]);
l /= 2, p /= 2;
}
return res;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k >> m;
tree_min.assign(rozmiar_drzewa,INF);
tree_max.assign(rozmiar_drzewa,-INF);
rep(i,n)
{
tree_min[i+base] = i, tree_max[i+base] = i;
}
while(m--)
{
cin >> a >> b;
--a,--b;
if(a <= b) update_max(a,a+k-1,b);
else update_min(a-k+1,a,b);
}
rep(i,n) A_min[0][i] = query_min(i);
rep(i,n) A_max[0][i] = query_max(i);
for(int i = 1; i <= LG; ++i)
{
rep(j,rozmiar_drzewa)
{
tree_minn[i-1][j] = INF, tree_maxx[i-1][j] = -INF;
}
rep(j,n)
{
tree_minn[i-1][j+base] = A_min[i-1][j], tree_maxx[i-1][j+base] = A_max[i-1][j];
}
for(int j = base-1; j > 0; --j)
{
tree_minn[i-1][j] = min(tree_minn[i-1][j*2],tree_minn[i-1][j*2+1]);
tree_maxx[i-1][j] = max(tree_maxx[i-1][j*2],tree_maxx[i-1][j*2+1]);
}
rep(j,n)
{
A_min[i][j] = min(A_min[i-1][j],query_min2(A_min[i-1][j],A_max[i-1][j],i-1)), A_max[i][j] = max(A_max[i-1][j],query_max2(A_min[i-1][j],A_max[i-1][j],i-1));
}
}
rep(i,rozmiar_drzewa)
{
tree_minn[LG][i] = INF, tree_maxx[LG][i] = -INF;
}
rep(i,n)
{
tree_minn[LG][i+base] = A_min[LG][i], tree_maxx[LG][i+base] = A_max[LG][i];
}
for(int i = base-1; i > 0; --i)
{
tree_minn[LG][i] = min(tree_minn[LG][i*2],tree_minn[LG][i*2+1]);
tree_maxx[LG][i] = max(tree_maxx[LG][i*2],tree_maxx[LG][i*2+1]);
}
cin >> q;
while(q--)
{
cin >> a >> b;
--a, --b;
if(a == b)
{
cout << "0" << '\n';
continue;
}
int l = a, p = a, wyn = 0;
for(int i = LG; i >= 0; --i)
{
int l_zap = min(l,query_min2(l,p,i)), p_zap = max(p,query_max2(l,p,i));
if(b < l_zap or b > p_zap)
{
l = l_zap, p = p_zap;
wyn += (1<<i);
}
}
if(wyn > n) cout << "-1" << '\n';
else cout << wyn+1 << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
39 ms |
105240 KB |
Output is correct |
2 |
Correct |
30 ms |
105208 KB |
Output is correct |
3 |
Correct |
33 ms |
105044 KB |
Output is correct |
4 |
Correct |
25 ms |
105344 KB |
Output is correct |
5 |
Correct |
33 ms |
105308 KB |
Output is correct |
6 |
Correct |
24 ms |
105292 KB |
Output is correct |
7 |
Correct |
25 ms |
105292 KB |
Output is correct |
8 |
Correct |
25 ms |
105204 KB |
Output is correct |
9 |
Correct |
24 ms |
105276 KB |
Output is correct |
10 |
Correct |
24 ms |
105188 KB |
Output is correct |
11 |
Correct |
28 ms |
105188 KB |
Output is correct |
12 |
Correct |
24 ms |
105188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
39 ms |
105240 KB |
Output is correct |
2 |
Correct |
30 ms |
105208 KB |
Output is correct |
3 |
Correct |
33 ms |
105044 KB |
Output is correct |
4 |
Correct |
25 ms |
105344 KB |
Output is correct |
5 |
Correct |
33 ms |
105308 KB |
Output is correct |
6 |
Correct |
24 ms |
105292 KB |
Output is correct |
7 |
Correct |
25 ms |
105292 KB |
Output is correct |
8 |
Correct |
25 ms |
105204 KB |
Output is correct |
9 |
Correct |
24 ms |
105276 KB |
Output is correct |
10 |
Correct |
24 ms |
105188 KB |
Output is correct |
11 |
Correct |
28 ms |
105188 KB |
Output is correct |
12 |
Correct |
24 ms |
105188 KB |
Output is correct |
13 |
Correct |
32 ms |
105272 KB |
Output is correct |
14 |
Correct |
30 ms |
105236 KB |
Output is correct |
15 |
Correct |
26 ms |
105308 KB |
Output is correct |
16 |
Correct |
33 ms |
105220 KB |
Output is correct |
17 |
Correct |
33 ms |
105304 KB |
Output is correct |
18 |
Correct |
31 ms |
105508 KB |
Output is correct |
19 |
Correct |
27 ms |
105308 KB |
Output is correct |
20 |
Correct |
31 ms |
105196 KB |
Output is correct |
21 |
Correct |
27 ms |
105292 KB |
Output is correct |
22 |
Correct |
30 ms |
105132 KB |
Output is correct |
23 |
Correct |
29 ms |
105248 KB |
Output is correct |
24 |
Correct |
29 ms |
105308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
243 ms |
105692 KB |
Output is correct |
2 |
Correct |
245 ms |
105776 KB |
Output is correct |
3 |
Correct |
288 ms |
105752 KB |
Output is correct |
4 |
Correct |
231 ms |
106036 KB |
Output is correct |
5 |
Correct |
180 ms |
105664 KB |
Output is correct |
6 |
Correct |
200 ms |
105756 KB |
Output is correct |
7 |
Correct |
203 ms |
105792 KB |
Output is correct |
8 |
Correct |
171 ms |
105760 KB |
Output is correct |
9 |
Correct |
149 ms |
105664 KB |
Output is correct |
10 |
Correct |
185 ms |
105704 KB |
Output is correct |
11 |
Correct |
191 ms |
105644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
321 ms |
105976 KB |
Output is correct |
2 |
Incorrect |
297 ms |
105964 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
566 ms |
105908 KB |
Output is correct |
2 |
Correct |
556 ms |
105956 KB |
Output is correct |
3 |
Correct |
496 ms |
106212 KB |
Output is correct |
4 |
Correct |
525 ms |
106020 KB |
Output is correct |
5 |
Correct |
264 ms |
106176 KB |
Output is correct |
6 |
Correct |
424 ms |
105924 KB |
Output is correct |
7 |
Correct |
331 ms |
106108 KB |
Output is correct |
8 |
Correct |
25 ms |
105276 KB |
Output is correct |
9 |
Correct |
30 ms |
105284 KB |
Output is correct |
10 |
Correct |
320 ms |
105796 KB |
Output is correct |
11 |
Correct |
342 ms |
105724 KB |
Output is correct |
12 |
Correct |
347 ms |
105704 KB |
Output is correct |
13 |
Correct |
359 ms |
105888 KB |
Output is correct |
14 |
Correct |
27 ms |
105192 KB |
Output is correct |
15 |
Correct |
33 ms |
105252 KB |
Output is correct |
16 |
Correct |
287 ms |
105956 KB |
Output is correct |
17 |
Correct |
544 ms |
106152 KB |
Output is correct |
18 |
Correct |
491 ms |
105936 KB |
Output is correct |
19 |
Correct |
498 ms |
106232 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
39 ms |
105240 KB |
Output is correct |
2 |
Correct |
30 ms |
105208 KB |
Output is correct |
3 |
Correct |
33 ms |
105044 KB |
Output is correct |
4 |
Correct |
25 ms |
105344 KB |
Output is correct |
5 |
Correct |
33 ms |
105308 KB |
Output is correct |
6 |
Correct |
24 ms |
105292 KB |
Output is correct |
7 |
Correct |
25 ms |
105292 KB |
Output is correct |
8 |
Correct |
25 ms |
105204 KB |
Output is correct |
9 |
Correct |
24 ms |
105276 KB |
Output is correct |
10 |
Correct |
24 ms |
105188 KB |
Output is correct |
11 |
Correct |
28 ms |
105188 KB |
Output is correct |
12 |
Correct |
24 ms |
105188 KB |
Output is correct |
13 |
Correct |
32 ms |
105272 KB |
Output is correct |
14 |
Correct |
30 ms |
105236 KB |
Output is correct |
15 |
Correct |
26 ms |
105308 KB |
Output is correct |
16 |
Correct |
33 ms |
105220 KB |
Output is correct |
17 |
Correct |
33 ms |
105304 KB |
Output is correct |
18 |
Correct |
31 ms |
105508 KB |
Output is correct |
19 |
Correct |
27 ms |
105308 KB |
Output is correct |
20 |
Correct |
31 ms |
105196 KB |
Output is correct |
21 |
Correct |
27 ms |
105292 KB |
Output is correct |
22 |
Correct |
30 ms |
105132 KB |
Output is correct |
23 |
Correct |
29 ms |
105248 KB |
Output is correct |
24 |
Correct |
29 ms |
105308 KB |
Output is correct |
25 |
Correct |
243 ms |
105692 KB |
Output is correct |
26 |
Correct |
245 ms |
105776 KB |
Output is correct |
27 |
Correct |
288 ms |
105752 KB |
Output is correct |
28 |
Correct |
231 ms |
106036 KB |
Output is correct |
29 |
Correct |
180 ms |
105664 KB |
Output is correct |
30 |
Correct |
200 ms |
105756 KB |
Output is correct |
31 |
Correct |
203 ms |
105792 KB |
Output is correct |
32 |
Correct |
171 ms |
105760 KB |
Output is correct |
33 |
Correct |
149 ms |
105664 KB |
Output is correct |
34 |
Correct |
185 ms |
105704 KB |
Output is correct |
35 |
Correct |
191 ms |
105644 KB |
Output is correct |
36 |
Correct |
321 ms |
105976 KB |
Output is correct |
37 |
Incorrect |
297 ms |
105964 KB |
Output isn't correct |
38 |
Halted |
0 ms |
0 KB |
- |