| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 441884 | rainboy | Pyramid Base (IOI08_pyramid_base) | C11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/* 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) {
if (upper - lower > 300)
a = (int) round(cbrt((long long) lower * (low ? lower : upper) * upper));
else
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;
}