/* discussed with Dukkha on performance optimization */
#if 1
#pragma GCC optimize("O3")
#endif
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define M 1000000
#define P 400000
int xmin[P], xmax[P], ymin[P], ymax[P], imin[P], imax[P], m, n, p, a;
short cc[P];
unsigned int b;
int iay[P * 2][3];
int compare_ymin(const void *a, const void *b) {
int i = *(int *) a;
int j = *(int *) b;
return ymin[i] - ymin[j];
}
int compare_ymax(const void *a, const void *b) {
int i = *(int *) a;
int j = *(int *) b;
return ymax[i] - ymax[j];
}
#define K (1 << 20)
unsigned int tt[K + K][2];
void push(int i) {
int j = 1, b;
for (b = K >> 1; b; b >>= 1) {
unsigned int x;
if ((x = tt[j][1])) {
int j0 = j * 2 + 0;
int j1 = j * 2 + 1;
tt[j0][0] += x, tt[j0][1] += x;
tt[j1][0] += x, tt[j1][1] += x;
tt[j][1] = 0;
}
j <<= 1;
if (i & b)
j ^= 1;
}
}
void update(int i, int c) { /* assumes i < K */
if (i <= 0)
return;
push(i);
i += K;
while (i > 1) {
int t0, t1;
if (i & 1)
tt[i ^ 1][0] += c, tt[i ^ 1][1] += c;
t0 = tt[i][0];
t1 = tt[i ^ 1][0];
tt[i >>= 1][0] = t0 < t1 ? t0 : t1;
}
}
unsigned int query(int i) {
unsigned int min = -1, t;
push(i);
i += K;
while (i > 1) {
if (i & 1 && min > (t = tt[i ^ 1][0]))
min = t;
i >>= 1;
}
return min;
}
void merge() {
int h, i, j;
for (i = j = 0; (h = i + j) < p + p; ) {
int *zz = iay[h];
if (j == p) {
zz[1] = 1;
zz[2] = ymin[zz[0] = imin[i++]] - a + 1;
} else if (i == p) {
zz[1] = 0;
zz[2] = ymax[zz[0] = imax[j++]] + 1;
} else {
int y1 = ymin[imin[i]] - a + 1;
int y0 = ymax[imax[j]] + 1;
if (y1 < y0) {
zz[0] = imin[i++];
zz[1] = 1;
zz[2] = y1;
} else {
zz[0] = imax[j++];
zz[1] = 0;
zz[2] = y0;
}
}
}
}
int check() {
int h, j, zero;
memset(tt, 0, sizeof tt);
if (b == 0) {
tt[1][0] = tt[1][1] = 1;
update(m - a + 1, -1);
}
merge();
zero = 0;
for (h = 0; h < p * 2; h = j) {
int y = iay[h][2];
if (y + a - 1 >= n) /* top boundary */
break;
if (!zero && y > 0) {
zero = 1;
if ((b ? query(m - a + 1) : tt[1][0]) <= b)
return 1;
}
for (j = h; j < p * 2 && iay[j][2] == y; j++) {
int i_ = iay[j][0];
int c = iay[j][1] ? cc[i_] : -cc[i_];
update(xmax[i_] + 1, c);
update(xmin[i_] - a + 1, -c);
}
if (y < 0) /* bottom boundary */
continue;
if ((b ? query(m - a + 1) : tt[1][0]) <= b)
return 1;
}
return 0;
}
#define getchar getchar_unlocked
int getint() {
int c, n;
while ((c = getchar()) < '0')
;
n = c - '0';
while ((c = getchar()) >= '0')
n = n * 10 + (c - '0');
return n;
}
int main() {
int i, lower, upper;
#if 0
scanf("%d%d%d%d", &m, &n, &b, &p);
#else
m = getint();
n = getint();
b = getint();
p = getint();
#endif
for (i = 0; i < p; i++) {
int x1, y1, x2, y2, c;
#if 0
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
#else
x1 = getint();
y1 = getint();
x2 = getint();
y2 = getint();
c = getint();
#endif
xmin[i] = x1 - 1;
xmax[i] = x2 - 1;
ymin[i] = y1 - 1;
ymax[i] = y2 - 1;
cc[i] = c;
imin[i] = imax[i] = i;
}
qsort(imin, p, sizeof *imin, compare_ymin);
qsort(imax, p, sizeof *imax, compare_ymax);
a = 1;
if (check()) {
int cnt = 0, low = 1;
lower = 1, upper = (m < n ? m : n) + 1;
while (upper - lower > 1) {
a = (lower + upper) / 2;
cnt++;
if (check()) {
lower = a;
low = 1;
} else {
upper = a;
low = 0;
}
}
} else
lower = 0;
printf("%d\n", lower);
return 0;
}
Compilation message
pyramid_base.c: In function 'main':
pyramid_base.c:196:16: warning: variable 'low' set but not used [-Wunused-but-set-variable]
196 | int cnt = 0, low = 1;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
16716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
16844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
16676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
16720 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
16716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
16716 KB |
Output is correct |
| 2 |
Correct |
10 ms |
16716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
16744 KB |
Output is correct |
| 2 |
Correct |
61 ms |
16716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
17104 KB |
Output is correct |
| 2 |
Correct |
61 ms |
17116 KB |
Output is correct |
| 3 |
Correct |
74 ms |
17100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
172 ms |
17896 KB |
Output is correct |
| 2 |
Correct |
249 ms |
17844 KB |
Output is correct |
| 3 |
Correct |
246 ms |
17904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
251 ms |
18380 KB |
Output is correct |
| 2 |
Correct |
121 ms |
18224 KB |
Output is correct |
| 3 |
Correct |
56 ms |
18124 KB |
Output is correct |
| 4 |
Correct |
520 ms |
18500 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
450 ms |
18884 KB |
Output is correct |
| 2 |
Correct |
642 ms |
18852 KB |
Output is correct |
| 3 |
Correct |
281 ms |
18844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
415 ms |
19184 KB |
Output is correct |
| 2 |
Correct |
814 ms |
19300 KB |
Output is correct |
| 3 |
Correct |
768 ms |
19176 KB |
Output is correct |
| 4 |
Correct |
830 ms |
19184 KB |
Output is correct |
| 5 |
Correct |
788 ms |
19216 KB |
Output is correct |
| 6 |
Correct |
300 ms |
19276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4416 ms |
33080 KB |
Output is correct |
| 2 |
Correct |
1426 ms |
32364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5024 ms |
41304 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5048 ms |
49352 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
