#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const int lim = 1e5;
int Log[lim+1];
template<class type, type (*F)(type, type), type def>
struct segtree{
struct node{
type sm, lazy_sm;
node(){
sm = def, lazy_sm = def;
}
node(type x){
sm = x, lazy_sm = def;
}
node operator+(node a){
return node(F(sm, a.sm));
}
void propagate(node a){
sm = F(sm, a.lazy_sm);
lazy_sm = F(lazy_sm, a.lazy_sm);
}
};
int k;
vector<node> v;
segtree(){}
segtree(int n){
k = 1;
while(k < n) k*=2;
k*=2;
v.resize(k);
}
void upd(int l, int r, int nd, int a, int b, type x){
if(a > r || b < l) return;
if(a >= l && b <= r){
v[nd].sm = F(v[nd].sm, x);
v[nd].lazy_sm = F(v[nd].lazy_sm, x);
return;
}
int md = (a+b)/2;
v[2*nd].propagate(v[nd]);
v[2*nd+1].propagate(v[nd]);
v[nd].lazy_sm = def;
upd(l, r, 2*nd, a, md, x);
upd(l, r, 2*nd+1, md+1, b, x);
v[nd] = v[2*nd]+v[2*nd+1];
}
void upd(int l, int r, type x){
upd(l, r, 1, 0, k/2-1, x);
}
type get(int l, int r, int nd, int a, int b){
if(a > r || b < l) return def;
if(a >= l && b <= r){
return v[nd].sm;
}
int md = (a+b)/2;
v[2*nd].propagate(v[nd]);
v[2*nd+1].propagate(v[nd]);
v[nd].lazy_sm = def;
type rt = F(get(l, r, 2*nd, a, md), get(l, r, 2*nd+1, md+1, b));
v[nd] = v[2*nd]+v[2*nd+1];
return rt;
}
type get(int l, int r){
return get(l, r, 1, 0, k/2-1);
}
};
template<class type, type (*F)(type, type), type def>
struct sparse_table{
vector<vector<type>> v;
sparse_table(){}
sparse_table(vector<type> _v){
int n = _v.size();
int k = 0, p = 1;
while(p < n) p*=2, k++;
k++;
v = vector<vector<type>>(n, vector<type>(k, def));
for(int i = 0; i < n; i++) v[i][0] = _v[i];
for(int p = 1; p < k; p++){
for(int i = 0; i < n; i++){
v[i][p] = F(v[i][p], v[i][p-1]);
if(i + (1<<(p-1)) < n) v[i][p] = F(v[i][p], v[i + (1<<(p-1))][p-1]);
}
}
}
type get(int a, int b){
int p = Log[b-a+1];
return F(v[a][p], v[b-(1<<p)+1][p]);
}
};
int MAX(int a, int b){return max(a, b);}
int MIN(int a, int b){return min(a, b);}
const int K = 18;
int n, m, k;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
for(int i = 1; i <= lim; i++) Log[i] = log2(i);
cin >> n >> k >> m;
segtree<int, MIN, lim+1> seg1(n);
segtree<int, MAX, -1> seg2(n);
vector<sparse_table<int, MIN, lim+1>> s1(K);
vector<sparse_table<int, MAX, -1>> s2(K);
for(int i = 0; i < n; i++) seg1.upd(i, i, i), seg2.upd(i, i, i);
while(m--){
int a, b; cin >> a >> b; a--, b--;
if(a < b) seg2.upd(a, min(a+k-1, b-1), b);
else{
swap(a, b);
seg1.upd(max(b-k+1, a+1), b, a);
}
}
vector<pair<int, int>> nxt(n);
vector<int> temp1, temp2;
for(int i = 0; i < n; i++){
int x = seg1.get(i, i), y = seg2.get(i, i);
temp1.pb(x);
temp2.pb(y);
nxt[i] = {x, y};
}
s1[0] = sparse_table<int, MIN, lim+1>(temp1);
s2[0] = sparse_table<int, MAX, -1>(temp2);
for(int P = 1; P < K; P++){
vector<int> temp1, temp2;
for(int i = 0; i < n; i++)
temp1.pb(s1[P-1].get(nxt[i].f, nxt[i].sc)),
temp2.pb(s2[P-1].get(nxt[i].f, nxt[i].sc));
s1[P] = sparse_table<int, MIN, lim+1>(temp1);
s2[P] = sparse_table<int, MAX, -1>(temp2);
for(int i = 0; i < n; i++){
pair<int, int> p = {s1[P].get(i, i), s2[P].get(i, i)};
nxt[i] = p;
}
}
int q; cin >> q;
while(q--){
int a, b; cin >> a >> b; a--, b--;
if(a < b){
if(s2[K-1].get(a, a) < b){
cout << "-1\n";
continue;
}
pair<int, int> p = {a, a};
int ans = 0;
while(1){
if(s2[0].get(p.f, p.sc) >= b){
ans++;
break;
}
for(int i = K-1; i >= 0; i--){
if(s2[i].get(p.f, p.sc) < b){
ans+=(1<<i);
p = {s1[i].get(p.f, p.sc), s2[i].get(p.f, p.sc)};
}
}
}
cout << ans << "\n";
}
else{
swap(a, b);
if(s1[K-1].get(b, b) > a){
cout << "-1\n";
continue;
}
pair<int, int> p = {b, b};
int ans = 0;
while(1){
if(s1[0].get(p.f, p.sc) <= a){
ans+=1;
break;
}
for(int i = K-1; i >= 0; i--){
if(s1[i].get(p.f, p.sc) > a){
ans+=(1<<i);
p = {s1[i].get(p.f, p.sc), s2[i].get(p.f, p.sc)};
}
}
}
cout << ans << "\n";
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1484 KB |
Output is correct |
2 |
Correct |
3 ms |
1468 KB |
Output is correct |
3 |
Correct |
3 ms |
1484 KB |
Output is correct |
4 |
Correct |
3 ms |
1484 KB |
Output is correct |
5 |
Correct |
3 ms |
1484 KB |
Output is correct |
6 |
Correct |
3 ms |
1484 KB |
Output is correct |
7 |
Correct |
3 ms |
1356 KB |
Output is correct |
8 |
Correct |
3 ms |
1484 KB |
Output is correct |
9 |
Correct |
3 ms |
1484 KB |
Output is correct |
10 |
Correct |
1 ms |
588 KB |
Output is correct |
11 |
Correct |
3 ms |
1484 KB |
Output is correct |
12 |
Correct |
3 ms |
1484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1484 KB |
Output is correct |
2 |
Correct |
3 ms |
1468 KB |
Output is correct |
3 |
Correct |
3 ms |
1484 KB |
Output is correct |
4 |
Correct |
3 ms |
1484 KB |
Output is correct |
5 |
Correct |
3 ms |
1484 KB |
Output is correct |
6 |
Correct |
3 ms |
1484 KB |
Output is correct |
7 |
Correct |
3 ms |
1356 KB |
Output is correct |
8 |
Correct |
3 ms |
1484 KB |
Output is correct |
9 |
Correct |
3 ms |
1484 KB |
Output is correct |
10 |
Correct |
1 ms |
588 KB |
Output is correct |
11 |
Correct |
3 ms |
1484 KB |
Output is correct |
12 |
Correct |
3 ms |
1484 KB |
Output is correct |
13 |
Correct |
14 ms |
6988 KB |
Output is correct |
14 |
Correct |
13 ms |
6988 KB |
Output is correct |
15 |
Correct |
13 ms |
7000 KB |
Output is correct |
16 |
Correct |
16 ms |
6936 KB |
Output is correct |
17 |
Correct |
17 ms |
6924 KB |
Output is correct |
18 |
Correct |
19 ms |
6968 KB |
Output is correct |
19 |
Correct |
17 ms |
6652 KB |
Output is correct |
20 |
Correct |
13 ms |
6988 KB |
Output is correct |
21 |
Correct |
12 ms |
7012 KB |
Output is correct |
22 |
Correct |
13 ms |
6948 KB |
Output is correct |
23 |
Correct |
13 ms |
6988 KB |
Output is correct |
24 |
Correct |
13 ms |
6956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
938 ms |
373964 KB |
Output is correct |
2 |
Correct |
908 ms |
373956 KB |
Output is correct |
3 |
Correct |
949 ms |
374068 KB |
Output is correct |
4 |
Correct |
985 ms |
374032 KB |
Output is correct |
5 |
Correct |
1012 ms |
374196 KB |
Output is correct |
6 |
Correct |
1004 ms |
374180 KB |
Output is correct |
7 |
Correct |
1032 ms |
373988 KB |
Output is correct |
8 |
Correct |
967 ms |
370604 KB |
Output is correct |
9 |
Correct |
1000 ms |
374100 KB |
Output is correct |
10 |
Correct |
1016 ms |
374056 KB |
Output is correct |
11 |
Correct |
1006 ms |
374048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1000 ms |
374320 KB |
Output is correct |
2 |
Correct |
1018 ms |
374100 KB |
Output is correct |
3 |
Correct |
1096 ms |
374428 KB |
Output is correct |
4 |
Correct |
1040 ms |
374096 KB |
Output is correct |
5 |
Correct |
1062 ms |
370636 KB |
Output is correct |
6 |
Correct |
1050 ms |
374116 KB |
Output is correct |
7 |
Correct |
1078 ms |
374224 KB |
Output is correct |
8 |
Correct |
1149 ms |
374260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1055 ms |
374184 KB |
Output is correct |
2 |
Correct |
1101 ms |
374228 KB |
Output is correct |
3 |
Correct |
1125 ms |
374304 KB |
Output is correct |
4 |
Correct |
1034 ms |
374304 KB |
Output is correct |
5 |
Correct |
977 ms |
374252 KB |
Output is correct |
6 |
Correct |
951 ms |
374160 KB |
Output is correct |
7 |
Correct |
931 ms |
374056 KB |
Output is correct |
8 |
Correct |
3 ms |
1484 KB |
Output is correct |
9 |
Correct |
13 ms |
6988 KB |
Output is correct |
10 |
Correct |
977 ms |
374012 KB |
Output is correct |
11 |
Correct |
1004 ms |
374132 KB |
Output is correct |
12 |
Correct |
988 ms |
370608 KB |
Output is correct |
13 |
Correct |
1059 ms |
374300 KB |
Output is correct |
14 |
Correct |
3 ms |
1484 KB |
Output is correct |
15 |
Correct |
13 ms |
6952 KB |
Output is correct |
16 |
Correct |
977 ms |
374060 KB |
Output is correct |
17 |
Correct |
1130 ms |
374176 KB |
Output is correct |
18 |
Correct |
1096 ms |
374440 KB |
Output is correct |
19 |
Correct |
1067 ms |
374252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1484 KB |
Output is correct |
2 |
Correct |
3 ms |
1468 KB |
Output is correct |
3 |
Correct |
3 ms |
1484 KB |
Output is correct |
4 |
Correct |
3 ms |
1484 KB |
Output is correct |
5 |
Correct |
3 ms |
1484 KB |
Output is correct |
6 |
Correct |
3 ms |
1484 KB |
Output is correct |
7 |
Correct |
3 ms |
1356 KB |
Output is correct |
8 |
Correct |
3 ms |
1484 KB |
Output is correct |
9 |
Correct |
3 ms |
1484 KB |
Output is correct |
10 |
Correct |
1 ms |
588 KB |
Output is correct |
11 |
Correct |
3 ms |
1484 KB |
Output is correct |
12 |
Correct |
3 ms |
1484 KB |
Output is correct |
13 |
Correct |
14 ms |
6988 KB |
Output is correct |
14 |
Correct |
13 ms |
6988 KB |
Output is correct |
15 |
Correct |
13 ms |
7000 KB |
Output is correct |
16 |
Correct |
16 ms |
6936 KB |
Output is correct |
17 |
Correct |
17 ms |
6924 KB |
Output is correct |
18 |
Correct |
19 ms |
6968 KB |
Output is correct |
19 |
Correct |
17 ms |
6652 KB |
Output is correct |
20 |
Correct |
13 ms |
6988 KB |
Output is correct |
21 |
Correct |
12 ms |
7012 KB |
Output is correct |
22 |
Correct |
13 ms |
6948 KB |
Output is correct |
23 |
Correct |
13 ms |
6988 KB |
Output is correct |
24 |
Correct |
13 ms |
6956 KB |
Output is correct |
25 |
Correct |
938 ms |
373964 KB |
Output is correct |
26 |
Correct |
908 ms |
373956 KB |
Output is correct |
27 |
Correct |
949 ms |
374068 KB |
Output is correct |
28 |
Correct |
985 ms |
374032 KB |
Output is correct |
29 |
Correct |
1012 ms |
374196 KB |
Output is correct |
30 |
Correct |
1004 ms |
374180 KB |
Output is correct |
31 |
Correct |
1032 ms |
373988 KB |
Output is correct |
32 |
Correct |
967 ms |
370604 KB |
Output is correct |
33 |
Correct |
1000 ms |
374100 KB |
Output is correct |
34 |
Correct |
1016 ms |
374056 KB |
Output is correct |
35 |
Correct |
1006 ms |
374048 KB |
Output is correct |
36 |
Correct |
1000 ms |
374320 KB |
Output is correct |
37 |
Correct |
1018 ms |
374100 KB |
Output is correct |
38 |
Correct |
1096 ms |
374428 KB |
Output is correct |
39 |
Correct |
1040 ms |
374096 KB |
Output is correct |
40 |
Correct |
1062 ms |
370636 KB |
Output is correct |
41 |
Correct |
1050 ms |
374116 KB |
Output is correct |
42 |
Correct |
1078 ms |
374224 KB |
Output is correct |
43 |
Correct |
1149 ms |
374260 KB |
Output is correct |
44 |
Correct |
1055 ms |
374184 KB |
Output is correct |
45 |
Correct |
1101 ms |
374228 KB |
Output is correct |
46 |
Correct |
1125 ms |
374304 KB |
Output is correct |
47 |
Correct |
1034 ms |
374304 KB |
Output is correct |
48 |
Correct |
977 ms |
374252 KB |
Output is correct |
49 |
Correct |
951 ms |
374160 KB |
Output is correct |
50 |
Correct |
931 ms |
374056 KB |
Output is correct |
51 |
Correct |
3 ms |
1484 KB |
Output is correct |
52 |
Correct |
13 ms |
6988 KB |
Output is correct |
53 |
Correct |
977 ms |
374012 KB |
Output is correct |
54 |
Correct |
1004 ms |
374132 KB |
Output is correct |
55 |
Correct |
988 ms |
370608 KB |
Output is correct |
56 |
Correct |
1059 ms |
374300 KB |
Output is correct |
57 |
Correct |
3 ms |
1484 KB |
Output is correct |
58 |
Correct |
13 ms |
6952 KB |
Output is correct |
59 |
Correct |
977 ms |
374060 KB |
Output is correct |
60 |
Correct |
1130 ms |
374176 KB |
Output is correct |
61 |
Correct |
1096 ms |
374440 KB |
Output is correct |
62 |
Correct |
1067 ms |
374252 KB |
Output is correct |
63 |
Correct |
1068 ms |
374276 KB |
Output is correct |
64 |
Correct |
1122 ms |
374304 KB |
Output is correct |
65 |
Correct |
1070 ms |
374432 KB |
Output is correct |
66 |
Correct |
993 ms |
374212 KB |
Output is correct |
67 |
Correct |
1122 ms |
374564 KB |
Output is correct |
68 |
Correct |
1008 ms |
370476 KB |
Output is correct |
69 |
Correct |
1004 ms |
374184 KB |
Output is correct |
70 |
Correct |
1040 ms |
374196 KB |
Output is correct |
71 |
Correct |
1120 ms |
374304 KB |
Output is correct |