#include <stdio.h>
#include <string.h>
#define N 100000
#define H 17 /* H = ceil(log2(N)) */
#define N_ (1 << H)
#define INF 0x3f3f3f3f
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
int n, n_;
int stmn[N_ * 2], stmx[N_ * 2];
void build1() {
int i;
memset(stmn, 0x3f, n_ * 2 * sizeof *stmn);
memset(stmx, -1, n_ * 2 * sizeof *stmx);
for (i = 0; i < n; i++)
stmn[n_ + i] = stmx[n_ + i] = i;
}
void update1(int l, int r, int x, int y) {
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
stmn[l] = min(stmn[l], x), stmx[l] = max(stmx[l], y), l++;
if ((r & 1) == 0)
stmn[r] = min(stmn[r], x), stmx[r] = max(stmx[r], y), r--;
}
}
void push1() {
int i;
for (i = 0; i < n_; i++) {
int l = i << 1, r = l | 1;
stmn[l] = min(stmn[l], stmn[i]), stmx[l] = max(stmx[l], stmx[i]);
stmn[r] = min(stmn[r], stmn[i]), stmx[r] = max(stmx[r], stmx[i]);
}
}
void pul2(int *stmn, int *stmx, int i) {
int l = i << 1, r = l | 1;
stmn[i] = min(stmn[l], stmn[r]);
stmx[i] = max(stmx[l], stmx[r]);
}
void build2(int *stmn, int *stmx, int *ll, int *rr) {
int i;
for (i = 0; i < n_; i++)
if (i < n)
stmn[n_ + i] = ll[i], stmx[n_ + i] = rr[i];
else
stmn[n_ + i] = INF, stmx[n_ + i] = -1;
for (i = n_ - 1; i > 0; i--)
pul2(stmn, stmx, i);
}
void query2(int *stmn, int *stmx, int l, int r, int *l_, int *r_) {
*l_ = INF, *r_ = -1;
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
*l_ = min(*l_, stmn[l]), *r_ = max(*r_, stmx[l]), l++;
if ((r & 1) == 0)
*l_ = min(*l_, stmn[r]), *r_ = max(*r_, stmx[r]), r--;
}
}
int main() {
static int stmn_[H + 1][N_ * 2], stmx_[H + 1][N_ * 2], ll[H + 1][N], rr[H + 1][N];
int k, q, m, h, i, j;
scanf("%d%d%d", &n, &k, &m);
n_ = 1;
while (n_ < n)
n_ <<= 1;
build1();
while (m--) {
scanf("%d%d", &i, &j), i--, j--;
if (i < j)
update1(i, min(i + k - 1, j - 1), INF, j);
else
update1(max(i - k + 1, j + 1), i, j, -1);
}
push1();
for (h = 0; h <= H; h++) {
if (h == 0)
for (i = 0; i < n; i++)
ll[0][i] = stmn[n_ + i], rr[0][i] = stmx[n_ + i];
else
for (i = 0; i < n; i++)
query2(stmn_[h - 1], stmx_[h - 1], ll[h - 1][i], rr[h - 1][i], &ll[h][i], &rr[h][i]);
build2(stmn_[h], stmx_[h], ll[h], rr[h]);
}
scanf("%d", &q);
while (q--) {
int l, r, l_, r_;
scanf("%d%d", &i, &j), i--, j--;
l = i, r = i;
query2(stmn_[H], stmx_[H], l, r, &l_, &r_);
if (j < l_ || j > r_) {
printf("-1\n");
continue;
}
k = 0;
for (h = H; h >= 0; h--) {
query2(stmn_[h], stmx_[h], l, r, &l_, &r_);
if (j < l_ || j > r_)
k += 1 << h, l = l_, r = r_;
}
printf("%d\n", k + 1);
}
return 0;
}
Compilation message
Main.c: In function 'main':
Main.c:78:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | scanf("%d%d%d", &n, &k, &m);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:84:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | scanf("%d%d", &i, &j), i--, j--;
| ^~~~~~~~~~~~~~~~~~~~~
Main.c:100:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
100 | scanf("%d", &q);
| ^~~~~~~~~~~~~~~
Main.c:104:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
104 | scanf("%d%d", &i, &j), i--, j--;
| ^~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
852 KB |
Output is correct |
2 |
Correct |
1 ms |
852 KB |
Output is correct |
3 |
Correct |
2 ms |
852 KB |
Output is correct |
4 |
Correct |
1 ms |
852 KB |
Output is correct |
5 |
Correct |
1 ms |
852 KB |
Output is correct |
6 |
Correct |
1 ms |
852 KB |
Output is correct |
7 |
Correct |
1 ms |
852 KB |
Output is correct |
8 |
Correct |
2 ms |
852 KB |
Output is correct |
9 |
Correct |
1 ms |
852 KB |
Output is correct |
10 |
Correct |
1 ms |
596 KB |
Output is correct |
11 |
Correct |
1 ms |
852 KB |
Output is correct |
12 |
Correct |
1 ms |
808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
852 KB |
Output is correct |
2 |
Correct |
1 ms |
852 KB |
Output is correct |
3 |
Correct |
2 ms |
852 KB |
Output is correct |
4 |
Correct |
1 ms |
852 KB |
Output is correct |
5 |
Correct |
1 ms |
852 KB |
Output is correct |
6 |
Correct |
1 ms |
852 KB |
Output is correct |
7 |
Correct |
1 ms |
852 KB |
Output is correct |
8 |
Correct |
2 ms |
852 KB |
Output is correct |
9 |
Correct |
1 ms |
852 KB |
Output is correct |
10 |
Correct |
1 ms |
596 KB |
Output is correct |
11 |
Correct |
1 ms |
852 KB |
Output is correct |
12 |
Correct |
1 ms |
808 KB |
Output is correct |
13 |
Correct |
8 ms |
1604 KB |
Output is correct |
14 |
Correct |
5 ms |
1524 KB |
Output is correct |
15 |
Correct |
3 ms |
1492 KB |
Output is correct |
16 |
Correct |
3 ms |
1620 KB |
Output is correct |
17 |
Correct |
5 ms |
1540 KB |
Output is correct |
18 |
Correct |
3 ms |
1492 KB |
Output is correct |
19 |
Correct |
4 ms |
1520 KB |
Output is correct |
20 |
Correct |
4 ms |
1492 KB |
Output is correct |
21 |
Correct |
3 ms |
1492 KB |
Output is correct |
22 |
Correct |
6 ms |
1612 KB |
Output is correct |
23 |
Correct |
4 ms |
1592 KB |
Output is correct |
24 |
Correct |
4 ms |
1584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
166 ms |
54180 KB |
Output is correct |
2 |
Correct |
166 ms |
54156 KB |
Output is correct |
3 |
Correct |
178 ms |
54412 KB |
Output is correct |
4 |
Correct |
144 ms |
54096 KB |
Output is correct |
5 |
Correct |
180 ms |
55560 KB |
Output is correct |
6 |
Correct |
175 ms |
55608 KB |
Output is correct |
7 |
Correct |
155 ms |
55360 KB |
Output is correct |
8 |
Correct |
183 ms |
54436 KB |
Output is correct |
9 |
Correct |
133 ms |
54416 KB |
Output is correct |
10 |
Correct |
211 ms |
55564 KB |
Output is correct |
11 |
Correct |
153 ms |
55612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
203 ms |
54988 KB |
Output is correct |
2 |
Correct |
186 ms |
56300 KB |
Output is correct |
3 |
Correct |
341 ms |
55172 KB |
Output is correct |
4 |
Correct |
179 ms |
55940 KB |
Output is correct |
5 |
Correct |
181 ms |
56216 KB |
Output is correct |
6 |
Correct |
175 ms |
56172 KB |
Output is correct |
7 |
Correct |
239 ms |
56212 KB |
Output is correct |
8 |
Correct |
261 ms |
56328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
219 ms |
56336 KB |
Output is correct |
2 |
Correct |
324 ms |
55324 KB |
Output is correct |
3 |
Correct |
291 ms |
54712 KB |
Output is correct |
4 |
Correct |
297 ms |
54456 KB |
Output is correct |
5 |
Correct |
184 ms |
54096 KB |
Output is correct |
6 |
Correct |
261 ms |
53924 KB |
Output is correct |
7 |
Correct |
195 ms |
55136 KB |
Output is correct |
8 |
Correct |
1 ms |
852 KB |
Output is correct |
9 |
Correct |
4 ms |
1520 KB |
Output is correct |
10 |
Correct |
202 ms |
55572 KB |
Output is correct |
11 |
Correct |
229 ms |
56180 KB |
Output is correct |
12 |
Correct |
276 ms |
56184 KB |
Output is correct |
13 |
Correct |
233 ms |
56196 KB |
Output is correct |
14 |
Correct |
2 ms |
812 KB |
Output is correct |
15 |
Correct |
5 ms |
1492 KB |
Output is correct |
16 |
Correct |
172 ms |
55612 KB |
Output is correct |
17 |
Correct |
359 ms |
56376 KB |
Output is correct |
18 |
Correct |
308 ms |
56340 KB |
Output is correct |
19 |
Correct |
325 ms |
56472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
852 KB |
Output is correct |
2 |
Correct |
1 ms |
852 KB |
Output is correct |
3 |
Correct |
2 ms |
852 KB |
Output is correct |
4 |
Correct |
1 ms |
852 KB |
Output is correct |
5 |
Correct |
1 ms |
852 KB |
Output is correct |
6 |
Correct |
1 ms |
852 KB |
Output is correct |
7 |
Correct |
1 ms |
852 KB |
Output is correct |
8 |
Correct |
2 ms |
852 KB |
Output is correct |
9 |
Correct |
1 ms |
852 KB |
Output is correct |
10 |
Correct |
1 ms |
596 KB |
Output is correct |
11 |
Correct |
1 ms |
852 KB |
Output is correct |
12 |
Correct |
1 ms |
808 KB |
Output is correct |
13 |
Correct |
8 ms |
1604 KB |
Output is correct |
14 |
Correct |
5 ms |
1524 KB |
Output is correct |
15 |
Correct |
3 ms |
1492 KB |
Output is correct |
16 |
Correct |
3 ms |
1620 KB |
Output is correct |
17 |
Correct |
5 ms |
1540 KB |
Output is correct |
18 |
Correct |
3 ms |
1492 KB |
Output is correct |
19 |
Correct |
4 ms |
1520 KB |
Output is correct |
20 |
Correct |
4 ms |
1492 KB |
Output is correct |
21 |
Correct |
3 ms |
1492 KB |
Output is correct |
22 |
Correct |
6 ms |
1612 KB |
Output is correct |
23 |
Correct |
4 ms |
1592 KB |
Output is correct |
24 |
Correct |
4 ms |
1584 KB |
Output is correct |
25 |
Correct |
166 ms |
54180 KB |
Output is correct |
26 |
Correct |
166 ms |
54156 KB |
Output is correct |
27 |
Correct |
178 ms |
54412 KB |
Output is correct |
28 |
Correct |
144 ms |
54096 KB |
Output is correct |
29 |
Correct |
180 ms |
55560 KB |
Output is correct |
30 |
Correct |
175 ms |
55608 KB |
Output is correct |
31 |
Correct |
155 ms |
55360 KB |
Output is correct |
32 |
Correct |
183 ms |
54436 KB |
Output is correct |
33 |
Correct |
133 ms |
54416 KB |
Output is correct |
34 |
Correct |
211 ms |
55564 KB |
Output is correct |
35 |
Correct |
153 ms |
55612 KB |
Output is correct |
36 |
Correct |
203 ms |
54988 KB |
Output is correct |
37 |
Correct |
186 ms |
56300 KB |
Output is correct |
38 |
Correct |
341 ms |
55172 KB |
Output is correct |
39 |
Correct |
179 ms |
55940 KB |
Output is correct |
40 |
Correct |
181 ms |
56216 KB |
Output is correct |
41 |
Correct |
175 ms |
56172 KB |
Output is correct |
42 |
Correct |
239 ms |
56212 KB |
Output is correct |
43 |
Correct |
261 ms |
56328 KB |
Output is correct |
44 |
Correct |
219 ms |
56336 KB |
Output is correct |
45 |
Correct |
324 ms |
55324 KB |
Output is correct |
46 |
Correct |
291 ms |
54712 KB |
Output is correct |
47 |
Correct |
297 ms |
54456 KB |
Output is correct |
48 |
Correct |
184 ms |
54096 KB |
Output is correct |
49 |
Correct |
261 ms |
53924 KB |
Output is correct |
50 |
Correct |
195 ms |
55136 KB |
Output is correct |
51 |
Correct |
1 ms |
852 KB |
Output is correct |
52 |
Correct |
4 ms |
1520 KB |
Output is correct |
53 |
Correct |
202 ms |
55572 KB |
Output is correct |
54 |
Correct |
229 ms |
56180 KB |
Output is correct |
55 |
Correct |
276 ms |
56184 KB |
Output is correct |
56 |
Correct |
233 ms |
56196 KB |
Output is correct |
57 |
Correct |
2 ms |
812 KB |
Output is correct |
58 |
Correct |
5 ms |
1492 KB |
Output is correct |
59 |
Correct |
172 ms |
55612 KB |
Output is correct |
60 |
Correct |
359 ms |
56376 KB |
Output is correct |
61 |
Correct |
308 ms |
56340 KB |
Output is correct |
62 |
Correct |
325 ms |
56472 KB |
Output is correct |
63 |
Correct |
269 ms |
55044 KB |
Output is correct |
64 |
Correct |
341 ms |
55220 KB |
Output is correct |
65 |
Correct |
311 ms |
55016 KB |
Output is correct |
66 |
Correct |
169 ms |
56308 KB |
Output is correct |
67 |
Correct |
302 ms |
56588 KB |
Output is correct |
68 |
Correct |
178 ms |
56196 KB |
Output is correct |
69 |
Correct |
173 ms |
56216 KB |
Output is correct |
70 |
Correct |
205 ms |
56332 KB |
Output is correct |
71 |
Correct |
330 ms |
56396 KB |
Output is correct |