#include <stdio.h>
#include <string.h>
#define N 1500000
#define Q 1000000
int max(int a, int b) { return a > b ? a : b; }
int tt[Q], ll[Q], rr[Q], xx_[Q], yy_[Q], zz[Q];
int n, q, s;
void solve_(int *hh, int q, int l, int r) {
int g, h;
for (h = l; h < r; h++)
if (tt[h] == 2) {
for (g = 0; g < q; g++)
if (yy_[hh[g]] <= zz[h])
xx_[hh[g]] = max(xx_[hh[g]], s - zz[h]);
} else if (tt[h] == 3) {
for (g = 0; g < q; g++)
if (xx_[hh[g]] <= zz[h])
yy_[hh[g]] = max(yy_[hh[g]], s - zz[h]);
}
}
void solve(int *hh, int q, int l, int r) {
int m, h1, h2, h3, tmp;
h1 = 0, h2 = 0, h3 = q;
while (h2 < h3)
if (ll[hh[h2]] <= l && r <= rr[hh[h2]])
h2++;
else if (ll[hh[h2]] < r && l < rr[hh[h2]]) {
tmp = hh[h1], hh[h1] = hh[h2], hh[h2] = tmp;
h1++, h2++;
} else {
h3--;
tmp = hh[h2], hh[h2] = hh[h3], hh[h3] = tmp;
}
solve_(hh + h1, h2 - h1, l, r);
if (r - l > 1) {
m = (l + r) / 2;
solve(hh, h1, l, m), solve(hh, h1, m, r);
}
}
int main() {
static int xx[N], yy[N], pp[N], hh[Q];
int m, h, i;
scanf("%d%d%d", &s, &n, &q);
for (i = 0; i < n; i++)
scanf("%d%d", &xx[i], &yy[i]);
memset(pp, -1, n * sizeof *pp);
for (h = 0; h < q; h++) {
scanf("%d", &tt[h]);
if (tt[h] == 1) {
scanf("%d", &i), i--;
ll[h] = pp[i] + 1, rr[h] = h, xx_[h] = xx[i], yy_[h] = yy[i];
} else if (tt[h] == 2 || tt[h] == 3)
scanf("%d", &zz[h]);
else
scanf("%d%d", &xx[n], &yy[n]), pp[n] = h, n++;
}
m = 0;
for (h = 0; h < q; h++)
if (tt[h] == 1)
hh[m++] = h;
solve(hh, m, 0, q);
for (h = 0; h < q; h++)
if (tt[h] == 1)
printf("%d %d\n", xx_[h], yy_[h]);
return 0;
}
Compilation message
sweeping.c: In function 'main':
sweeping.c:52:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | scanf("%d%d%d", &s, &n, &q);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
sweeping.c:54:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | scanf("%d%d", &xx[i], &yy[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sweeping.c:57:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | scanf("%d", &tt[h]);
| ^~~~~~~~~~~~~~~~~~~
sweeping.c:59:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%d", &i), i--;
| ^~~~~~~~~~~~~~~
sweeping.c:62:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
62 | scanf("%d", &zz[h]);
| ^~~~~~~~~~~~~~~~~~~
sweeping.c:64:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | scanf("%d%d", &xx[n], &yy[n]), pp[n] = h, n++;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
596 KB |
Output is correct |
| 2 |
Correct |
7 ms |
596 KB |
Output is correct |
| 3 |
Correct |
3 ms |
596 KB |
Output is correct |
| 4 |
Correct |
8 ms |
596 KB |
Output is correct |
| 5 |
Correct |
3 ms |
468 KB |
Output is correct |
| 6 |
Correct |
9 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18017 ms |
53516 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18088 ms |
51256 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18088 ms |
51256 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
596 KB |
Output is correct |
| 2 |
Correct |
7 ms |
596 KB |
Output is correct |
| 3 |
Correct |
3 ms |
596 KB |
Output is correct |
| 4 |
Correct |
8 ms |
596 KB |
Output is correct |
| 5 |
Correct |
3 ms |
468 KB |
Output is correct |
| 6 |
Correct |
9 ms |
468 KB |
Output is correct |
| 7 |
Execution timed out |
18017 ms |
53516 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
