// 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(min(s + k, ab[u].SE), 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:223:44: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
223 | REP (i, 1, n + 1 - (1 << k - 1)) {
| ~~^~~
Main.cpp:8:49: note: in definition of macro 'REP'
8 | #define REP(i, s, e) for (int i = (s); i < (e); i++)
| ^
Main.cpp:224:72: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
224 | sp[k][i] = max(sp[k - 1][i], sp[k - 1][i + (1 << k - 1)]);
| ~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
28 ms |
46164 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
28 ms |
46164 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
63 ms |
76956 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
51 ms |
24476 KB |
Output is correct |
| 2 |
Correct |
99 ms |
26696 KB |
Output is correct |
| 3 |
Correct |
48 ms |
24912 KB |
Output is correct |
| 4 |
Correct |
71 ms |
26456 KB |
Output is correct |
| 5 |
Correct |
99 ms |
26496 KB |
Output is correct |
| 6 |
Correct |
99 ms |
26452 KB |
Output is correct |
| 7 |
Correct |
85 ms |
26596 KB |
Output is correct |
| 8 |
Correct |
87 ms |
26716 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
83 ms |
57968 KB |
Output is correct |
| 2 |
Correct |
53 ms |
55892 KB |
Output is correct |
| 3 |
Correct |
41 ms |
55120 KB |
Output is correct |
| 4 |
Correct |
32 ms |
52908 KB |
Output is correct |
| 5 |
Correct |
24 ms |
52460 KB |
Output is correct |
| 6 |
Correct |
25 ms |
52572 KB |
Output is correct |
| 7 |
Correct |
41 ms |
24892 KB |
Output is correct |
| 8 |
Correct |
4 ms |
37208 KB |
Output is correct |
| 9 |
Correct |
6 ms |
41308 KB |
Output is correct |
| 10 |
Correct |
52 ms |
57028 KB |
Output is correct |
| 11 |
Correct |
94 ms |
26448 KB |
Output is correct |
| 12 |
Correct |
59 ms |
57560 KB |
Output is correct |
| 13 |
Correct |
59 ms |
57404 KB |
Output is correct |
| 14 |
Correct |
4 ms |
37212 KB |
Output is correct |
| 15 |
Correct |
6 ms |
41564 KB |
Output is correct |
| 16 |
Correct |
52 ms |
57056 KB |
Output is correct |
| 17 |
Correct |
81 ms |
26708 KB |
Output is correct |
| 18 |
Correct |
83 ms |
57684 KB |
Output is correct |
| 19 |
Correct |
88 ms |
57536 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
28 ms |
46164 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
