#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 = 1e5+5, base = (1<<17), rozmiar_drzewa = base * 2, INF = 1e9+50;
int n = 0, k = 0, m = 0, q = 0, a = 0, b = 0;
vector<int> tree_min;
vector<int> tree_max;
int lewy[MAXN];
int prawy[MAXN];
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)
{
l = l + base - 1, p = p + base + 1;
int res = INF;
while(l / 2 != p / 2)
{
if(l % 2 == 0) res = min(res,tree_min[l+1]);
if(p % 2 == 1) res = min(res,tree_min[p-1]);
l /= 2, p /= 2;
}
return res;
}
inline int query_max2(int l, int p)
{
l = l + base - 1, p = p + base + 1;
int res = -INF;
while(l / 2 != p / 2)
{
if(l % 2 == 0) res = max(res,tree_max[l+1]);
if(p % 2 == 1) res = max(res,tree_max[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) lewy[i] = query_min(i);
rep(i,n) prawy[i] = query_max(i);
//rep(i,n) cout << lewy[i] << " " << prawy[i] << endl;
tree_min.assign(rozmiar_drzewa,INF);
tree_max.assign(rozmiar_drzewa,-INF);
rep(i,n)
{
tree_min[i+base] = lewy[i], tree_max[i+base] = prawy[i];
}
for(int i = base - 1; i > 0; --i)
{
tree_min[i] = min(tree_min[i*2],tree_min[i*2+1]);
tree_max[i] = max(tree_max[i*2],tree_max[i*2+1]);
}
cin >> q;
while(q--)
{
cin >> a >> b;
--a, --b;
if(a == b)
{
cout << "0" << '\n';
continue;
}
int akt_l = a, akt_p = a, wyn = -1;
for(int i = 1; i < n; ++i)
{
int l = query_min2(akt_l,akt_p), p = query_max2(akt_l,akt_p);
//cout << "akt L: " << akt_l << " akt P: " << akt_p << " L: " << l << " P: " << p << endl;
akt_l = l, akt_p = p;
if(b >= akt_l and b <= akt_p)
{
wyn = i;
break;
}
}
cout << wyn << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2392 KB |
Output is correct |
2 |
Correct |
3 ms |
2392 KB |
Output is correct |
3 |
Correct |
2 ms |
2396 KB |
Output is correct |
4 |
Correct |
5 ms |
2396 KB |
Output is correct |
5 |
Correct |
3 ms |
2396 KB |
Output is correct |
6 |
Correct |
2 ms |
2548 KB |
Output is correct |
7 |
Correct |
2 ms |
2392 KB |
Output is correct |
8 |
Correct |
2 ms |
2392 KB |
Output is correct |
9 |
Correct |
2 ms |
2548 KB |
Output is correct |
10 |
Correct |
2 ms |
2396 KB |
Output is correct |
11 |
Correct |
2 ms |
2396 KB |
Output is correct |
12 |
Correct |
2 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2392 KB |
Output is correct |
2 |
Correct |
3 ms |
2392 KB |
Output is correct |
3 |
Correct |
2 ms |
2396 KB |
Output is correct |
4 |
Correct |
5 ms |
2396 KB |
Output is correct |
5 |
Correct |
3 ms |
2396 KB |
Output is correct |
6 |
Correct |
2 ms |
2548 KB |
Output is correct |
7 |
Correct |
2 ms |
2392 KB |
Output is correct |
8 |
Correct |
2 ms |
2392 KB |
Output is correct |
9 |
Correct |
2 ms |
2548 KB |
Output is correct |
10 |
Correct |
2 ms |
2396 KB |
Output is correct |
11 |
Correct |
2 ms |
2396 KB |
Output is correct |
12 |
Correct |
2 ms |
2396 KB |
Output is correct |
13 |
Correct |
178 ms |
2900 KB |
Output is correct |
14 |
Correct |
119 ms |
2392 KB |
Output is correct |
15 |
Correct |
2 ms |
2392 KB |
Output is correct |
16 |
Correct |
184 ms |
2568 KB |
Output is correct |
17 |
Correct |
47 ms |
2596 KB |
Output is correct |
18 |
Correct |
2 ms |
2396 KB |
Output is correct |
19 |
Correct |
2 ms |
2396 KB |
Output is correct |
20 |
Correct |
2 ms |
2392 KB |
Output is correct |
21 |
Correct |
2 ms |
2396 KB |
Output is correct |
22 |
Correct |
4 ms |
2396 KB |
Output is correct |
23 |
Correct |
9 ms |
2396 KB |
Output is correct |
24 |
Correct |
28 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
4144 KB |
Output is correct |
2 |
Correct |
20 ms |
4124 KB |
Output is correct |
3 |
Correct |
22 ms |
4304 KB |
Output is correct |
4 |
Correct |
20 ms |
4060 KB |
Output is correct |
5 |
Runtime error |
52 ms |
6344 KB |
Execution killed with signal 6 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
64 ms |
4688 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2035 ms |
5432 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2392 KB |
Output is correct |
2 |
Correct |
3 ms |
2392 KB |
Output is correct |
3 |
Correct |
2 ms |
2396 KB |
Output is correct |
4 |
Correct |
5 ms |
2396 KB |
Output is correct |
5 |
Correct |
3 ms |
2396 KB |
Output is correct |
6 |
Correct |
2 ms |
2548 KB |
Output is correct |
7 |
Correct |
2 ms |
2392 KB |
Output is correct |
8 |
Correct |
2 ms |
2392 KB |
Output is correct |
9 |
Correct |
2 ms |
2548 KB |
Output is correct |
10 |
Correct |
2 ms |
2396 KB |
Output is correct |
11 |
Correct |
2 ms |
2396 KB |
Output is correct |
12 |
Correct |
2 ms |
2396 KB |
Output is correct |
13 |
Correct |
178 ms |
2900 KB |
Output is correct |
14 |
Correct |
119 ms |
2392 KB |
Output is correct |
15 |
Correct |
2 ms |
2392 KB |
Output is correct |
16 |
Correct |
184 ms |
2568 KB |
Output is correct |
17 |
Correct |
47 ms |
2596 KB |
Output is correct |
18 |
Correct |
2 ms |
2396 KB |
Output is correct |
19 |
Correct |
2 ms |
2396 KB |
Output is correct |
20 |
Correct |
2 ms |
2392 KB |
Output is correct |
21 |
Correct |
2 ms |
2396 KB |
Output is correct |
22 |
Correct |
4 ms |
2396 KB |
Output is correct |
23 |
Correct |
9 ms |
2396 KB |
Output is correct |
24 |
Correct |
28 ms |
2396 KB |
Output is correct |
25 |
Correct |
20 ms |
4144 KB |
Output is correct |
26 |
Correct |
20 ms |
4124 KB |
Output is correct |
27 |
Correct |
22 ms |
4304 KB |
Output is correct |
28 |
Correct |
20 ms |
4060 KB |
Output is correct |
29 |
Runtime error |
52 ms |
6344 KB |
Execution killed with signal 6 |
30 |
Halted |
0 ms |
0 KB |
- |