#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vei;
typedef vector<vei> vevei;
#define all(a) (a).begin(), (a).end()
#define sz(a) (int) a.size()
#define con cout << "NO\n"
#define coe cout << "YES\n";
#define str string
#define pb push_back
#define ff first
#define sc second
#define ss second
#define pii pair<int, int>
#define mxe max_element
#define mne min_element
#define stf shrink_to_fit
#define f(i, l, r) for (int i = (l); i < (r); i++)
#define double ld
struct segtree {
int n, tim;
vector<pair<int, int>> t;
segtree() = default;
segtree(int n_) {
n = n_;
tim = 0;
t.resize(4 * n, { 0, -1 });
}
void upd(int v, int tl, int tr, int l, int r, int x) {
if (l <= tl && tr <= r) {
t[v] = { x, tim };
return;
}
if (tr <= l || tl >= r) return;
int tm = (tl + tr) / 2;
upd(v * 2, tl, tm, l, r, x);
upd(v * 2 + 1, tm, tr, l, r, x);
}
pair<int, int> get(int v, int tl, int tr, int x) {
if (tl + 1 == tr) {
return t[v];
}
int tm = (tl + tr) / 2;
pair<int, int> res;
if (x < tm) {
res = get(v * 2, tl, tm, x);
}
else {
res = get(v * 2 + 1, tm, tr, x);
}
if (res.sc > t[v].sc) return res;
else return t[v];
}
};
const int MAXN = 100010;
vector<int> Log_2(MAXN, 0);
void fill() {
for (int i = 2; i < MAXN; i++) {
Log_2[i] = Log_2[i / 2] + 1;
}
}
struct SparseTableMax {
int n;
vector<int> a;
vector<vector<int>> mx;
SparseTableMax(int n_, vector<int> a_) {
n = n_;
a = a_;
mx.resize(Log_2[n] + 1, vector<int>(n, -1));
build();
}
int comp(int i, int j) {
return (a[i] > a[j] ? i : j);
}
void build() {
for (int i = n - 1; i >= 0; i--) {
mx[0][i] = i;
int st = 1;
while ((1 << st) + i <= n) {
mx[st][i] = comp(mx[st - 1][i], mx[st - 1][(1 << (st - 1)) + i]);
st++;
}
}
}
int req(int l, int r) {
bool sw = false;
int sz = r - l + 1;
int otr1 = mx[Log_2[sz]][l];
int ot2 = mx[Log_2[sz]][r - (1 << Log_2[sz]) + 1];
return comp(otr1, ot2);
}
};
struct SparseTableMin {
int n;
vector<int> a;
vector<vector<int>> mx;
SparseTableMin(int n_, vector<int> a_) {
n = n_;
a = a_;
mx.resize(Log_2[n] + 1, vector<int>(n, -1));
build();
}
int comp(int i, int j) {
return (a[i] < a[j] ? i : j);
}
void build() {
for (int i = n - 1; i >= 0; i--) {
mx[0][i] = i;
int st = 1;
while ((1 << st) + i <= n) {
mx[st][i] = comp(mx[st - 1][i], mx[st - 1][(1 << (st - 1)) + i]);
st++;
}
}
}
int req(int l, int r) {
bool sw = false;
int sz = r - l + 1;
int otr1 = mx[Log_2[sz]][l];
int ot2 = mx[Log_2[sz]][r - (1 << Log_2[sz]) + 1];
return comp(otr1, ot2);
}
};
int bfs(int n, vector<vector<int>> g, int s, int gl) {
vector<int> d(n, -1);
d[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
auto v = q.front();
q.pop();
for (auto& u : g[v]) {
if (d[u] == -1) {
d[u] = d[v] + 1;
q.push(u);
}
}
}
return d[gl];
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
fill();
int n, k; cin >> n >> k;
int m; cin >> m;
vector<pair<int, int>> a(m);
f(i, 0, m) {
cin >> a[i].ff >> a[i].sc;
a[i].ff--;
a[i].sc--;
}
int q; cin >> q;
vector<pair<int, int>> req(q);
f(i, 0, q) {
cin >> req[i].ff >> req[i].sc;
req[i].ff--;
req[i].sc--;
}
vector<pair<int, int>> tor, tol;
f(i, 0, m) {
if (a[i].ff < a[i].sc) {
tor.pb(a[i]);
}
else {
tol.pb(a[i]);
}
}
segtree sg(n);
f(i, 0, n) {
sg.upd(1, 0, n, i, i + 1, i);
}
sort(all(tor), [](pair<int, int> a, pair<int, int> b) {
return a.sc < b.sc;
});
for (int i = 0; i < sz(tor); i++) {
sg.tim++;
sg.upd(1, 0, n, tor[i].ff, min(tor[i].sc + 1, tor[i].ff + k), tor[i].sc);
}
sort(all(tol), [](pair<int, int> a, pair<int, int> b) {
return a.sc < b.sc;
});
segtree sg2(n);
f(i, 0, n) {
sg2.upd(1, 0, n, i, i + 1, i);
}
for (int i = sz(tol) - 1; i >= 0; i--) {
sg2.tim++;
sg2.upd(1, 0, n, max(tol[i].ff - k + 1, tol[i].sc), tol[i].ff + 1, tol[i].sc);
}
vector<pair<int, int>> seg1(n);
f(i, 0, n) {
seg1[i] = { sg2.get(1, 0, n, i).ff, sg.get(1, 0, n, i).ff };
}
vector<int> RIGHT(n), LEFT(n);
f(i, 0, n) {
RIGHT[i] = seg1[i].sc;
LEFT[i] = seg1[i].ff;
}
SparseTableMax sp(n, RIGHT);
SparseTableMin sp2(n, LEFT);
vector<pair<int, int>> g(n);
for (int i = 0; i < n; i++) {
int ir = sp.req(seg1[i].ff, seg1[i].sc);
int il = sp2.req(seg1[i].ff, seg1[i].sc);
g[i] = { il, ir };
}
vector<vector<pair<int, int>>> up(n, vector<pair<int, int>>(19));
f(i, 0, n) up[i][0] = g[i];
auto comp_r = [&](int i, int j) {
return (RIGHT[i] < RIGHT[j] ? j : i);
};
auto comp_l = [&](int i, int j) {
return (LEFT[i] > LEFT[j] ? j : i);
};
for (int j = 1; j < 19; j++) {
for (int i = 0; i < n; i++) {
auto p = up[i][j - 1];
auto p2 = up[p.ff][j - 1], p3 = up[p.sc][j - 1];
int l_ind = comp_l(p2.ff, comp_l(p2.sc, comp_l(p3.ff, p3.sc)));
int r_ind = comp_r(p2.ff, comp_r(p2.sc, comp_r(p3.ff, p3.sc)));
up[i][j] = { l_ind, r_ind };
}
}
for (auto& u : req) {
if (u.ff == u.sc) {
cout << "0\n";
continue;
}
if (LEFT[u.ff] <= u.sc && u.sc <= RIGHT[u.ff]) {
cout << "1\n";
continue;
}
auto rs = up[u.ff][18];
if (u.sc < LEFT[rs.ff] || u.sc > RIGHT[rs.sc]) {
cout << "-1\n";
continue;
}
int ans = 0;
int LF = u.ff, RG = u.ff;
for (int j = 18; j >= 0; j--) {
auto rs1 = up[LF][j], rs2 = up[RG][j];
int l_ind = comp_l(rs1.ff, comp_l(rs1.sc, comp_l(rs2.ff, rs2.sc)));
int r_ind = comp_r(rs1.ff, comp_r(rs1.sc, comp_r(rs2.ff, rs2.sc)));
if (u.sc < LEFT[l_ind] || u.sc > RIGHT[r_ind]) {
LF = l_ind;
RG = r_ind;
ans += (1 << j);
}
}
assert(ans + 2 <= n);
cout << ans + 2 << '\n';
}
return 0;
}
Compilation message
Main.cpp: In member function 'int SparseTableMax::req(int, int)':
Main.cpp:103:14: warning: unused variable 'sw' [-Wunused-variable]
103 | bool sw = false;
| ^~
Main.cpp: In member function 'int SparseTableMin::req(int, int)':
Main.cpp:139:14: warning: unused variable 'sw' [-Wunused-variable]
139 | bool sw = false;
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
856 KB |
Output is correct |
2 |
Correct |
1 ms |
860 KB |
Output is correct |
3 |
Correct |
1 ms |
1112 KB |
Output is correct |
4 |
Correct |
1 ms |
860 KB |
Output is correct |
5 |
Correct |
1 ms |
860 KB |
Output is correct |
6 |
Correct |
1 ms |
860 KB |
Output is correct |
7 |
Correct |
1 ms |
856 KB |
Output is correct |
8 |
Correct |
1 ms |
860 KB |
Output is correct |
9 |
Correct |
1 ms |
860 KB |
Output is correct |
10 |
Correct |
1 ms |
860 KB |
Output is correct |
11 |
Correct |
1 ms |
860 KB |
Output is correct |
12 |
Correct |
1 ms |
860 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
856 KB |
Output is correct |
2 |
Correct |
1 ms |
860 KB |
Output is correct |
3 |
Correct |
1 ms |
1112 KB |
Output is correct |
4 |
Correct |
1 ms |
860 KB |
Output is correct |
5 |
Correct |
1 ms |
860 KB |
Output is correct |
6 |
Correct |
1 ms |
860 KB |
Output is correct |
7 |
Correct |
1 ms |
856 KB |
Output is correct |
8 |
Correct |
1 ms |
860 KB |
Output is correct |
9 |
Correct |
1 ms |
860 KB |
Output is correct |
10 |
Correct |
1 ms |
860 KB |
Output is correct |
11 |
Correct |
1 ms |
860 KB |
Output is correct |
12 |
Correct |
1 ms |
860 KB |
Output is correct |
13 |
Correct |
3 ms |
1628 KB |
Output is correct |
14 |
Correct |
3 ms |
1628 KB |
Output is correct |
15 |
Correct |
2 ms |
1372 KB |
Output is correct |
16 |
Correct |
3 ms |
1436 KB |
Output is correct |
17 |
Correct |
3 ms |
1628 KB |
Output is correct |
18 |
Correct |
3 ms |
1628 KB |
Output is correct |
19 |
Correct |
3 ms |
1628 KB |
Output is correct |
20 |
Correct |
3 ms |
1628 KB |
Output is correct |
21 |
Correct |
2 ms |
1624 KB |
Output is correct |
22 |
Correct |
3 ms |
1628 KB |
Output is correct |
23 |
Correct |
3 ms |
1628 KB |
Output is correct |
24 |
Correct |
3 ms |
1628 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
111 ms |
43768 KB |
Output is correct |
2 |
Correct |
124 ms |
43732 KB |
Output is correct |
3 |
Correct |
120 ms |
44664 KB |
Output is correct |
4 |
Correct |
117 ms |
43584 KB |
Output is correct |
5 |
Correct |
153 ms |
46784 KB |
Output is correct |
6 |
Correct |
128 ms |
46780 KB |
Output is correct |
7 |
Correct |
152 ms |
46732 KB |
Output is correct |
8 |
Correct |
137 ms |
43736 KB |
Output is correct |
9 |
Correct |
130 ms |
44316 KB |
Output is correct |
10 |
Correct |
138 ms |
47160 KB |
Output is correct |
11 |
Correct |
141 ms |
46996 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
144 ms |
44728 KB |
Output is correct |
2 |
Correct |
173 ms |
48076 KB |
Output is correct |
3 |
Correct |
165 ms |
45216 KB |
Output is correct |
4 |
Correct |
142 ms |
47616 KB |
Output is correct |
5 |
Correct |
162 ms |
47568 KB |
Output is correct |
6 |
Correct |
178 ms |
47808 KB |
Output is correct |
7 |
Correct |
165 ms |
47976 KB |
Output is correct |
8 |
Correct |
183 ms |
48128 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
179 ms |
48072 KB |
Output is correct |
2 |
Correct |
164 ms |
45264 KB |
Output is correct |
3 |
Correct |
145 ms |
43968 KB |
Output is correct |
4 |
Correct |
124 ms |
43456 KB |
Output is correct |
5 |
Correct |
116 ms |
42816 KB |
Output is correct |
6 |
Correct |
116 ms |
42564 KB |
Output is correct |
7 |
Correct |
123 ms |
45200 KB |
Output is correct |
8 |
Correct |
1 ms |
856 KB |
Output is correct |
9 |
Correct |
3 ms |
1624 KB |
Output is correct |
10 |
Correct |
163 ms |
46920 KB |
Output is correct |
11 |
Correct |
158 ms |
47816 KB |
Output is correct |
12 |
Correct |
170 ms |
47436 KB |
Output is correct |
13 |
Correct |
172 ms |
47808 KB |
Output is correct |
14 |
Correct |
1 ms |
860 KB |
Output is correct |
15 |
Correct |
3 ms |
1628 KB |
Output is correct |
16 |
Correct |
141 ms |
47028 KB |
Output is correct |
17 |
Correct |
182 ms |
48072 KB |
Output is correct |
18 |
Correct |
167 ms |
48072 KB |
Output is correct |
19 |
Correct |
174 ms |
48304 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
856 KB |
Output is correct |
2 |
Correct |
1 ms |
860 KB |
Output is correct |
3 |
Correct |
1 ms |
1112 KB |
Output is correct |
4 |
Correct |
1 ms |
860 KB |
Output is correct |
5 |
Correct |
1 ms |
860 KB |
Output is correct |
6 |
Correct |
1 ms |
860 KB |
Output is correct |
7 |
Correct |
1 ms |
856 KB |
Output is correct |
8 |
Correct |
1 ms |
860 KB |
Output is correct |
9 |
Correct |
1 ms |
860 KB |
Output is correct |
10 |
Correct |
1 ms |
860 KB |
Output is correct |
11 |
Correct |
1 ms |
860 KB |
Output is correct |
12 |
Correct |
1 ms |
860 KB |
Output is correct |
13 |
Correct |
3 ms |
1628 KB |
Output is correct |
14 |
Correct |
3 ms |
1628 KB |
Output is correct |
15 |
Correct |
2 ms |
1372 KB |
Output is correct |
16 |
Correct |
3 ms |
1436 KB |
Output is correct |
17 |
Correct |
3 ms |
1628 KB |
Output is correct |
18 |
Correct |
3 ms |
1628 KB |
Output is correct |
19 |
Correct |
3 ms |
1628 KB |
Output is correct |
20 |
Correct |
3 ms |
1628 KB |
Output is correct |
21 |
Correct |
2 ms |
1624 KB |
Output is correct |
22 |
Correct |
3 ms |
1628 KB |
Output is correct |
23 |
Correct |
3 ms |
1628 KB |
Output is correct |
24 |
Correct |
3 ms |
1628 KB |
Output is correct |
25 |
Correct |
111 ms |
43768 KB |
Output is correct |
26 |
Correct |
124 ms |
43732 KB |
Output is correct |
27 |
Correct |
120 ms |
44664 KB |
Output is correct |
28 |
Correct |
117 ms |
43584 KB |
Output is correct |
29 |
Correct |
153 ms |
46784 KB |
Output is correct |
30 |
Correct |
128 ms |
46780 KB |
Output is correct |
31 |
Correct |
152 ms |
46732 KB |
Output is correct |
32 |
Correct |
137 ms |
43736 KB |
Output is correct |
33 |
Correct |
130 ms |
44316 KB |
Output is correct |
34 |
Correct |
138 ms |
47160 KB |
Output is correct |
35 |
Correct |
141 ms |
46996 KB |
Output is correct |
36 |
Correct |
144 ms |
44728 KB |
Output is correct |
37 |
Correct |
173 ms |
48076 KB |
Output is correct |
38 |
Correct |
165 ms |
45216 KB |
Output is correct |
39 |
Correct |
142 ms |
47616 KB |
Output is correct |
40 |
Correct |
162 ms |
47568 KB |
Output is correct |
41 |
Correct |
178 ms |
47808 KB |
Output is correct |
42 |
Correct |
165 ms |
47976 KB |
Output is correct |
43 |
Correct |
183 ms |
48128 KB |
Output is correct |
44 |
Correct |
179 ms |
48072 KB |
Output is correct |
45 |
Correct |
164 ms |
45264 KB |
Output is correct |
46 |
Correct |
145 ms |
43968 KB |
Output is correct |
47 |
Correct |
124 ms |
43456 KB |
Output is correct |
48 |
Correct |
116 ms |
42816 KB |
Output is correct |
49 |
Correct |
116 ms |
42564 KB |
Output is correct |
50 |
Correct |
123 ms |
45200 KB |
Output is correct |
51 |
Correct |
1 ms |
856 KB |
Output is correct |
52 |
Correct |
3 ms |
1624 KB |
Output is correct |
53 |
Correct |
163 ms |
46920 KB |
Output is correct |
54 |
Correct |
158 ms |
47816 KB |
Output is correct |
55 |
Correct |
170 ms |
47436 KB |
Output is correct |
56 |
Correct |
172 ms |
47808 KB |
Output is correct |
57 |
Correct |
1 ms |
860 KB |
Output is correct |
58 |
Correct |
3 ms |
1628 KB |
Output is correct |
59 |
Correct |
141 ms |
47028 KB |
Output is correct |
60 |
Correct |
182 ms |
48072 KB |
Output is correct |
61 |
Correct |
167 ms |
48072 KB |
Output is correct |
62 |
Correct |
174 ms |
48304 KB |
Output is correct |
63 |
Correct |
145 ms |
44604 KB |
Output is correct |
64 |
Correct |
158 ms |
45232 KB |
Output is correct |
65 |
Correct |
185 ms |
44600 KB |
Output is correct |
66 |
Correct |
166 ms |
47960 KB |
Output is correct |
67 |
Correct |
175 ms |
48068 KB |
Output is correct |
68 |
Correct |
169 ms |
47548 KB |
Output is correct |
69 |
Correct |
164 ms |
47852 KB |
Output is correct |
70 |
Correct |
170 ms |
48096 KB |
Output is correct |
71 |
Correct |
169 ms |
48140 KB |
Output is correct |