// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 200005;
const int MAXM = 200005;
const int MAXQ = 200005;
const int MAXL = 20;
int n, k, m;
ii ab[MAXM];
int q;
ii st[MAXQ];
namespace st4 {
int p[MAXL][MAXN];
int mx[MAXN];
int ans[MAXQ];
int par[MAXN], rnk[MAXN], rt[MAXN];
void init() {
REP (i, 1, n + 2) {
par[i] = i;
rnk[i] = 1;
rt[i] = i;
}
}
int findp(int i) {
if (par[i] == i) {
return i;
}
return par[i] = findp(par[i]);
}
bool join(int a, int b) {
int pa = findp(a), pb = findp(b);
if (pa == pb) {
return 0;
}
if (rnk[pa] < rnk[pb]) {
swap(pa, pb);
}
if (rnk[pa] == rnk[pb]) {
rnk[pa]++;
}
par[pb] = pa;
mxto(rt[pa], rt[pb]);
return 1;
}
void solve() {
sort(ab, ab + m, [&] (ii l, ii r) {
return l.FI < r.FI;
});
REP (i, 1, n + 1) {
p[0][i] = -1;
}
int prv = 0;
REP (i, 0, m) {
auto [a, b] = ab[i];
if (a > b) {
continue;
}
REP (j, max(prv, a), b + 1) {
cerr << j << ": " << a << '\n';
p[0][j] = a;
}
mxto(prv, b + 1);
}
REP (k, 1, MAXL) {
REP (i, 1, n + 1) {
if (p[k - 1][i] == -1) {
p[k][i] = -1;
} else {
p[k][i] = p[k - 1][p[k - 1][i]];
}
}
}
sort(ab, ab + m, [&] (ii l, ii r) {
return l.SE > r.SE;
});
init();
REP (i, 1, n + 1) {
mx[i] = i;
}
REP (i, 0, m) {
auto [a, b] = ab[i];
if (a > b) {
continue;
}
while (rt[findp(a)] < min(a + k, b)) {
assert(mxto(mx[rt[findp(a)]], b));
join(rt[findp(a)], rt[findp(a)] + 1);
}
}
REP (i, 0, q) {
auto [s, t] = st[i];
if (s > t) {
continue;
}
int res = 0;
RREP (k, MAXL - 1, 0) {
if (p[k][t] != -1 && p[k][t] > s) {
t = p[k][t];
res += 1 << k;
}
}
if (mx[s] >= t) {
ans[i] = res + 1;
} else {
ans[i] = -1;
}
}
}
int main() {
solve();
REP (i, 0, m) {
ab[i].FI = n - ab[i].FI + 1;
ab[i].SE = n - ab[i].SE + 1;
}
REP (i, 0, q) {
st[i].FI = n - st[i].FI + 1;
st[i].SE = n - st[i].SE + 1;
}
solve();
REP (i, 0, q) {
cout << ans[i] << '\n';
}
return 0;
}
}
namespace st5 {
int p[MAXL][MAXM];
int ans[MAXQ];
ii sp[MAXL][MAXN];
ii qmx(int s, int e) {
int k = 31 - __builtin_clz(e - s + 1);
return max(sp[k][s], sp[k][e - (1 << k) + 1]);
}
int par[MAXN], rnk[MAXN], rt[MAXN];
void init() {
REP (i, 1, n + 2) {
par[i] = i;
rnk[i] = 1;
rt[i] = i;
}
}
int findp(int i) {
if (par[i] == i) {
return i;
}
return par[i] = findp(par[i]);
}
bool join(int a, int b) {
int pa = findp(a), pb = findp(b);
if (pa == pb) {
return 0;
}
if (rnk[pa] < rnk[pb]) {
swap(pa, pb);
}
if (rnk[pa] == rnk[pb]) {
rnk[pa]++;
}
par[pb] = pa;
mxto(rt[pa], rt[pb]);
return 1;
}
int main() {
sort(ab, ab + m, [&] (ii l, ii r) {
return l.SE > r.SE;
});
init();
REP (i, 1, n + 1) {
sp[0][i] = {i, -1};
}
REP (i, 0, m) {
auto [a, b] = ab[i];
if (a > b) {
continue;
}
while (rt[findp(a)] < min(a + k, b)) {
assert(mxto(sp[0][rt[findp(a)]], {b, i}));
join(rt[findp(a)], rt[findp(a)] + 1);
}
}
REP (i, 1, n + 1) {
cerr << i << ": " << sp[0][i].FI << ' ' << sp[0][i].SE << '\n';
}
REP (k, 1, MAXL) {
REP (i, 1, n + 1 - (1 << k - 1)) {
sp[k][i] = max(sp[k - 1][i], sp[k - 1][i + (1 << k - 1)]);
}
}
REP (i, 0, m) {
auto [a, b] = ab[i];
p[0][i] = qmx(a, b).SE;
}
REP (k, 1, MAXL) {
REP (i, 0, m + 1) {
if (p[k - 1][i] == -1) {
p[k][i] = -1;
} else {
p[k][i] = p[k - 1][p[k - 1][i]];
}
}
}
REP (i, 0, q) {
auto [s, t] = st[i];
if (s > t) {
continue;
}
int u = sp[0][s].SE;
cerr << ' ' << u << '\n';
if (u == -1) {
ans[i] = -1;
continue;
}
if (ab[u].SE >= t) {
ans[i] = 1;
continue;
}
int nu = qmx(s + 1, ab[u].SE).SE;
cerr << " " << nu << '\n';
if (nu == -1 || nu == u) {
ans[i] = -1;
continue;
}
u = nu;
ans[i] = 2;
if (ab[u].SE >= t) {
continue;
}
RREP (k, MAXL - 1, 0) {
if (p[k][u] != -1 && ab[p[k][u]].SE < t) {
u = p[k][u];
ans[i] += 1 << k;
}
}
cerr << " " << u << '\n';
if (p[0][u] == -1 || ab[p[0][u]].SE < t) {
ans[i] = -1;
} else {
ans[i]++;
}
}
REP (i, 0, q) {
cout << ans[i] << '\n';
}
return 0;
}
}
int main() {
#ifndef DEBUG
ios::sync_with_stdio(0), cin.tie(0);
#endif
cin >> n >> k >> m;
REP (i, 0, m) {
cin >> ab[i].FI >> ab[i].SE;
}
cin >> q;
REP (i, 0, q) {
cin >> st[i].FI >> st[i].SE;
}
if (k == n - 1) {
st4::main();
} else {
st5::main();
}
return 0;
}
Compilation message
Main.cpp: In function 'int st5::main()':
Main.cpp:224:40: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
224 | REP (i, 1, n + 1 - (1 << k - 1)) {
| ~~^~~
Main.cpp:9:45: note: in definition of macro 'REP'
9 | #define REP(i, s, e) for (int i = (s); i < (e); i++)
| ^
Main.cpp:225:68: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
225 | sp[k][i] = max(sp[k - 1][i], sp[k - 1][i + (1 << k - 1)]);
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
41 ms |
30900 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
11124 KB |
Output is correct |
| 2 |
Correct |
114 ms |
12228 KB |
Output is correct |
| 3 |
Correct |
62 ms |
11452 KB |
Output is correct |
| 4 |
Correct |
91 ms |
12128 KB |
Output is correct |
| 5 |
Correct |
119 ms |
11880 KB |
Output is correct |
| 6 |
Correct |
113 ms |
11976 KB |
Output is correct |
| 7 |
Correct |
99 ms |
12152 KB |
Output is correct |
| 8 |
Correct |
104 ms |
12132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
32576 KB |
Output is correct |
| 2 |
Correct |
75 ms |
24212 KB |
Output is correct |
| 3 |
Correct |
49 ms |
19860 KB |
Output is correct |
| 4 |
Correct |
37 ms |
17240 KB |
Output is correct |
| 5 |
Correct |
27 ms |
15956 KB |
Output is correct |
| 6 |
Correct |
25 ms |
15624 KB |
Output is correct |
| 7 |
Correct |
54 ms |
11208 KB |
Output is correct |
| 8 |
Correct |
1 ms |
468 KB |
Output is correct |
| 9 |
Correct |
1 ms |
852 KB |
Output is correct |
| 10 |
Correct |
67 ms |
31772 KB |
Output is correct |
| 11 |
Correct |
114 ms |
11976 KB |
Output is correct |
| 12 |
Correct |
75 ms |
32460 KB |
Output is correct |
| 13 |
Correct |
76 ms |
32480 KB |
Output is correct |
| 14 |
Correct |
1 ms |
468 KB |
Output is correct |
| 15 |
Correct |
2 ms |
852 KB |
Output is correct |
| 16 |
Correct |
65 ms |
31820 KB |
Output is correct |
| 17 |
Correct |
98 ms |
14996 KB |
Output is correct |
| 18 |
Correct |
105 ms |
35500 KB |
Output is correct |
| 19 |
Correct |
95 ms |
35504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
