| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 723116 |
2023-04-13T08:54:09 Z |
finn__ |
Golf (JOI17_golf) |
C++17 |
|
3416 ms |
1048576 KB |
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <stdint.h>
#include <stdbool.h>
#define N 100009
#define X (1LL << 30)
typedef int L;
/* Range Set Point Query Segment Tree */
typedef struct Node Node;
struct Node
{
Node *l, *r;
L x, z;
};
void propagate(Node *node)
{
if (!node->l)
{
node->l = (Node *)calloc(1, sizeof *node->l);
node->l->x = -X, node->l->z = 0;
}
if (!node->r)
{
node->r = (Node *)calloc(1, sizeof *node->r);
node->r->x = -X, node->r->z = 0;
}
if (node->z)
{
node->l->x = node->z;
node->l->z = node->z;
node->r->x = node->z;
node->r->z = node->z;
node->z = 0;
}
}
void set(Node *node, L i, L j, L x, L a, L b)
{
if (b < i || a > j)
return;
if (i <= a && b <= j)
node->x = x, node->z = x;
else
{
propagate(node);
set(node->l, i, j, x, a, (a + b) / 2);
set(node->r, i, j, x, (a + b) / 2 + 1, b);
}
}
L query(Node *node, L i, L a, L b)
{
if (a == b)
return node->x;
if (node->z)
return node->z;
if (i <= (a + b) / 2)
return node->l ? query(node->l, i, a, (a + b) / 2) : -(X - 1);
else
return node->r ? query(node->r, i, (a + b) / 2 + 1, b) : -(X - 1);
}
void reset(Node *node)
{
if (node->l)
reset(node->l), free(node->l), node->l = 0;
if (node->r)
reset(node->r), free(node->r), node->r = 0;
}
/* Segment Tree for managing intervals */
typedef struct NodeY NodeY;
struct NodeY
{
NodeY *l, *r;
size_t x; /* interval count in internal nodes, index in leaf nodes */
};
bool insertIntervalY(NodeY *node, L k, size_t x, L a, L b)
{
if (a == b)
{
if (node->x)
return 0;
node->x = x + 1; /* + 1, since 0 signifies there is no interval */
return 1;
}
else
{
if (k <= (a + b) / 2)
{
if (!node->l)
node->l = (NodeY *)calloc(1, sizeof *node->l);
bool inserted = insertIntervalY(node->l, k, x, a, (a + b) / 2);
node->x += inserted;
return inserted;
}
else
{
if (!node->r)
node->r = (NodeY *)calloc(1, sizeof *node->r);
bool inserted = insertIntervalY(node->r, k, x, (a + b) / 2 + 1, b);
node->x += inserted;
return inserted;
}
}
}
size_t getNextIntervalY(NodeY *node, L i, L j, L a, L b)
{
if (b < i || a > j)
return SIZE_MAX;
if (i <= a && b <= j)
{
if (!node->x)
return SIZE_MAX;
while (node->l || node->r)
node = (node->l && node->l->x) ? node->l : node->r;
return node->x - 1;
}
else
{
size_t x = SIZE_MAX;
if (node->l)
x = getNextIntervalY(node->l, i, j, a, (a + b) / 2);
if (x == SIZE_MAX && node->r)
x = getNextIntervalY(node->r, i, j, (a + b) / 2 + 1, b);
return x;
}
}
void removeIntervalY(NodeY *node, L k, L a, L b)
{
if (a == b)
node->x = 0;
else
{
--node->x;
if (k <= (a + b) / 2)
removeIntervalY(node->l, k, a, (a + b) / 2);
else
removeIntervalY(node->r, k, (a + b) / 2 + 1, b);
}
}
typedef struct NodeX NodeX;
struct NodeX
{
NodeX *l, *r;
NodeY *y;
};
void insertIntervalX(NodeX *node, L i, L j, L k, size_t x, L a, L b)
{
if (b < i || a > j)
return;
if (i <= a && b <= j)
{
if (!node->y)
node->y = (NodeY *)calloc(1, sizeof *node->y);
insertIntervalY(node->y, k, x, 0, X - 1);
}
else
{
if (!node->l)
node->l = (NodeX *)calloc(1, sizeof *node->l);
if (!node->r)
node->r = (NodeX *)calloc(1, sizeof *node->r);
insertIntervalX(node->l, i, j, k, x, a, (a + b) / 2);
insertIntervalX(node->r, i, j, k, x, (a + b) / 2 + 1, b);
}
}
size_t getNextIntervalX(NodeX *node, L i, L j, L k, L a, L b)
{
size_t x = node->y ? getNextIntervalY(node->y, i, j, 0, X - 1) : SIZE_MAX;
if (x != SIZE_MAX || a == b)
return x;
if (k <= (a + b) / 2)
return node->l ? getNextIntervalX(node->l, i, j, k, a, (a + b) / 2) : SIZE_MAX;
return node->r ? getNextIntervalX(node->r, i, j, k, (a + b) / 2 + 1, b) : SIZE_MAX;
}
void removeIntervalX(NodeX *node, L i, L j, L k, L a, L b)
{
if (b < i || a > j)
return;
if (i <= a && b <= j)
removeIntervalY(node->y, k, 0, X - 1);
else
{
removeIntervalX(node->l, i, j, k, a, (a + b) / 2);
removeIntervalX(node->r, i, j, k, (a + b) / 2 + 1, b);
}
}
size_t min(size_t x, size_t y) { return x < y ? x : y; }
L max(L x, L y) { return x > y ? x : y; }
int cmp0(void const *a, void const *b) { return *(L *)a - *(L *)b; }
int cmp1(void const *a, void const *b) { return *((L *)a + 1) - *((L *)b + 1); }
int cmp2(void const *a, void const *b) { return *((L *)a + 2) - *((L *)b + 2); }
int cmp3(void const *a, void const *b) { return *((L *)a + 3) - *((L *)b + 3); }
int cmp4(void const *a, void const *b) { return *((L *)a + 4) - *((L *)b + 4); }
L r[N][5], s[N][4], t[4 * N][2];
size_t queue[4 * N], distance[4 * N];
Node root;
NodeX horizontal, vertical;
int main()
{
L S, T, U, V;
size_t n;
scanf("%lld %lld %lld %lld %zu", &S, &T, &U, &V, &n);
for (size_t i = 0; i < n; i++)
{
scanf("%lld %lld %lld %lld", r[i], r[i] + 1, r[i] + 2, r[i] + 3);
s[i][0] = r[i][0];
s[i][1] = r[i][1];
s[i][2] = r[i][2];
s[i][3] = r[i][3];
r[i][4] = i;
}
/* Start and end point are rectangles with 0 area */
r[n][0] = r[n][1] = s[n][0] = s[n][1] = S;
r[n][2] = r[n][3] = s[n][2] = s[n][3] = T;
r[n][4] = n;
++n;
r[n][0] = r[n][1] = s[n][0] = s[n][1] = U;
r[n][2] = r[n][3] = s[n][2] = s[n][3] = V;
r[n][4] = n;
++n;
/* Sweep x ascending */
qsort(r, n, sizeof *r, cmp0);
qsort(s, n, sizeof *s, cmp1);
root.x = root.z = -(X - 1);
size_t i = 0, j = 0;
while (i < n)
{
while (j < n && r[i][0] >= s[j][1])
{
if (s[j][2] + 1 <= s[j][3] - 1)
set(&root, s[j][2] + 1, s[j][3] - 1, s[j][1], 0, X - 1);
++j;
}
t[4 * r[i][4]][0] = max(0, query(&root, r[i][2], 0, X - 1));
t[4 * r[i][4] + 1][0] = max(0, query(&root, r[i][3], 0, X - 1));
++i;
}
/* Sweep x descending */
for (size_t i = 0; i < n; i++)
r[i][0] *= -1, r[i][1] *= -1, s[i][0] *= -1, s[i][1] *= -1;
qsort(r, n, sizeof *r, cmp1);
qsort(s, n, sizeof *s, cmp0);
reset(&root);
root.x = root.z = -(X - 1);
i = j = 0;
while (i < n)
{
while (j < n && r[i][1] >= s[j][0])
{
if (s[j][2] + 1 <= s[j][3] - 1)
set(&root, s[j][2] + 1, s[j][3] - 1, s[j][0], 0, X - 1);
++j;
}
t[4 * r[i][4]][1] = -query(&root, r[i][2], 0, X - 1);
t[4 * r[i][4] + 1][1] = -query(&root, r[i][3], 0, X - 1);
++i;
}
for (size_t i = 0; i < n; i++)
r[i][0] *= -1, r[i][1] *= -1, s[i][0] *= -1, s[i][1] *= -1;
/* Sweep y ascending */
qsort(r, n, sizeof *r, cmp2);
qsort(s, n, sizeof *s, cmp3);
reset(&root);
root.x = root.z = -(X - 1);
i = j = 0;
while (i < n)
{
while (j < n && r[i][2] >= s[j][3])
{
if (s[j][0] + 1 <= s[j][1] - 1)
set(&root, s[j][0] + 1, s[j][1] - 1, s[j][3], 0, X - 1);
++j;
}
t[4 * r[i][4] + 2][0] = max(0, query(&root, r[i][0], 0, X - 1));
t[4 * r[i][4] + 3][0] = max(0, query(&root, r[i][1], 0, X - 1));
++i;
}
/* Sweep y descending */
for (size_t i = 0; i < n; i++)
r[i][2] *= -1, r[i][3] *= -1, s[i][2] *= -1, s[i][3] *= -1;
qsort(r, n, sizeof *r, cmp3);
qsort(s, n, sizeof *s, cmp2);
reset(&root);
root.x = root.z = -(X - 1);
i = j = 0;
while (i < n)
{
while (j < n && r[i][3] >= s[j][2])
{
if (s[j][0] + 1 <= s[j][1] - 1)
set(&root, s[j][0] + 1, s[j][1] - 1, s[j][2], 0, X - 1);
++j;
}
t[4 * r[i][4] + 2][1] = -query(&root, r[i][0], 0, X - 1);
t[4 * r[i][4] + 3][1] = -query(&root, r[i][1], 0, X - 1);
++i;
}
for (size_t i = 0; i < n; i++)
r[i][2] *= -1, r[i][3] *= -1, s[i][2] *= -1, s[i][3] *= -1;
/* Be patient, the real algorithm starts now... */
if ((S == U && t[4 * (n - 2) + 1][0] <= V && V <= t[4 * (n - 2) + 1][1]) ||
(T == V && t[4 * (n - 2)][0] <= U && U <= t[4 * (n - 2)][1]))
{
printf("1\n");
return 0;
}
qsort(r, n, sizeof *r, cmp4);
insertIntervalX(&horizontal, t[4 * (n - 1)][0], t[4 * (n - 1)][1],
V, 4 * (n - 1), 0, X - 1);
insertIntervalX(&vertical, t[4 * (n - 1) + 2][0], t[4 * (n - 1) + 2][1],
U, 4 * (n - 1) + 2, 0, X - 1);
for (size_t i = 0; i < 4 * (n - 2); i++)
{
if ((i & 3) < 2)
insertIntervalX(&horizontal, t[i][0], t[i][1], r[i >> 2][(i + 2) & 3], i, 0, X - 1);
else
insertIntervalX(&vertical, t[i][0], t[i][1], r[i >> 2][(i + 2) & 3], i, 0, X - 1);
}
i = j = 0;
queue[j++] = 4 * (n - 2);
queue[j++] = 4 * (n - 2) + 2;
distance[4 * (n - 2)] = distance[4 * (n - 2) + 2] = 1;
while (i < j)
{
size_t const u = queue[i++];
size_t v = getNextIntervalX((u & 3) < 2 ? &vertical : &horizontal,
t[u][0], t[u][1], r[u >> 2][(u + 2) & 3], 0, X - 1);
while (v != SIZE_MAX)
{
distance[v] = distance[u] + 1;
queue[j++] = v;
removeIntervalX((v & 3) < 2 ? &horizontal : &vertical,
t[v][0], t[v][1], r[v >> 2][(v + 2) & 3], 0, X - 1);
v = getNextIntervalX((u & 3) < 2 ? &vertical : &horizontal,
t[u][0], t[u][1], r[u >> 2][(u + 2) & 3], 0, X - 1);
}
}
printf("%zu\n", min(distance[4 * (n - 1)], distance[4 * (n - 1) + 2]));
}
Compilation message
golf.cpp: In function 'int main()':
golf.cpp:221:15: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'L*' {aka 'int*'} [-Wformat=]
221 | scanf("%lld %lld %lld %lld %zu", &S, &T, &U, &V, &n);
| ~~~^ ~~
| | |
| long long int* L* {aka int*}
| %d
golf.cpp:221:20: warning: format '%lld' expects argument of type 'long long int*', but argument 3 has type 'L*' {aka 'int*'} [-Wformat=]
221 | scanf("%lld %lld %lld %lld %zu", &S, &T, &U, &V, &n);
| ~~~^ ~~
| | |
| long long int* L* {aka int*}
| %d
golf.cpp:221:25: warning: format '%lld' expects argument of type 'long long int*', but argument 4 has type 'L*' {aka 'int*'} [-Wformat=]
221 | scanf("%lld %lld %lld %lld %zu", &S, &T, &U, &V, &n);
| ~~~^ ~~
| | |
| long long int* L* {aka int*}
| %d
golf.cpp:221:30: warning: format '%lld' expects argument of type 'long long int*', but argument 5 has type 'L*' {aka 'int*'} [-Wformat=]
221 | scanf("%lld %lld %lld %lld %zu", &S, &T, &U, &V, &n);
| ~~~^ ~~
| | |
| long long int* L* {aka int*}
| %d
golf.cpp:224:19: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'L*' {aka 'int*'} [-Wformat=]
224 | scanf("%lld %lld %lld %lld", r[i], r[i] + 1, r[i] + 2, r[i] + 3);
| ~~~^ ~~~~
| | |
| long long int* L* {aka int*}
| %d
golf.cpp:224:24: warning: format '%lld' expects argument of type 'long long int*', but argument 3 has type 'L*' {aka 'int*'} [-Wformat=]
224 | scanf("%lld %lld %lld %lld", r[i], r[i] + 1, r[i] + 2, r[i] + 3);
| ~~~^ ~~~~~~~~
| | |
| long long int* L* {aka int*}
| %d
golf.cpp:224:29: warning: format '%lld' expects argument of type 'long long int*', but argument 4 has type 'L*' {aka 'int*'} [-Wformat=]
224 | scanf("%lld %lld %lld %lld", r[i], r[i] + 1, r[i] + 2, r[i] + 3);
| ~~~^ ~~~~~~~~
| | |
| long long int* L* {aka int*}
| %d
golf.cpp:224:34: warning: format '%lld' expects argument of type 'long long int*', but argument 5 has type 'L*' {aka 'int*'} [-Wformat=]
224 | scanf("%lld %lld %lld %lld", r[i], r[i] + 1, r[i] + 2, r[i] + 3);
| ~~~^ ~~~~~~~~
| | |
| long long int* L* {aka int*}
| %d
golf.cpp:221:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
221 | scanf("%lld %lld %lld %lld %zu", &S, &T, &U, &V, &n);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:224:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
224 | scanf("%lld %lld %lld %lld", r[i], r[i] + 1, r[i] + 2, r[i] + 3);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
544 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1364 KB |
Output is correct |
| 5 |
Correct |
28 ms |
5076 KB |
Output is correct |
| 6 |
Correct |
25 ms |
5076 KB |
Output is correct |
| 7 |
Correct |
24 ms |
4692 KB |
Output is correct |
| 8 |
Correct |
27 ms |
5092 KB |
Output is correct |
| 9 |
Correct |
27 ms |
5100 KB |
Output is correct |
| 10 |
Correct |
27 ms |
5060 KB |
Output is correct |
| 11 |
Correct |
26 ms |
5120 KB |
Output is correct |
| 12 |
Correct |
30 ms |
5008 KB |
Output is correct |
| 13 |
Correct |
31 ms |
4948 KB |
Output is correct |
| 14 |
Correct |
26 ms |
4948 KB |
Output is correct |
| 15 |
Correct |
8 ms |
1364 KB |
Output is correct |
| 16 |
Correct |
15 ms |
2564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
544 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1364 KB |
Output is correct |
| 5 |
Correct |
28 ms |
5076 KB |
Output is correct |
| 6 |
Correct |
25 ms |
5076 KB |
Output is correct |
| 7 |
Correct |
24 ms |
4692 KB |
Output is correct |
| 8 |
Correct |
27 ms |
5092 KB |
Output is correct |
| 9 |
Correct |
27 ms |
5100 KB |
Output is correct |
| 10 |
Correct |
27 ms |
5060 KB |
Output is correct |
| 11 |
Correct |
26 ms |
5120 KB |
Output is correct |
| 12 |
Correct |
30 ms |
5008 KB |
Output is correct |
| 13 |
Correct |
31 ms |
4948 KB |
Output is correct |
| 14 |
Correct |
26 ms |
4948 KB |
Output is correct |
| 15 |
Correct |
8 ms |
1364 KB |
Output is correct |
| 16 |
Correct |
15 ms |
2564 KB |
Output is correct |
| 17 |
Correct |
154 ms |
80960 KB |
Output is correct |
| 18 |
Correct |
167 ms |
81596 KB |
Output is correct |
| 19 |
Correct |
177 ms |
81100 KB |
Output is correct |
| 20 |
Correct |
161 ms |
81140 KB |
Output is correct |
| 21 |
Correct |
161 ms |
83404 KB |
Output is correct |
| 22 |
Correct |
176 ms |
82732 KB |
Output is correct |
| 23 |
Correct |
161 ms |
81520 KB |
Output is correct |
| 24 |
Correct |
155 ms |
82000 KB |
Output is correct |
| 25 |
Correct |
172 ms |
80832 KB |
Output is correct |
| 26 |
Correct |
157 ms |
81868 KB |
Output is correct |
| 27 |
Correct |
24 ms |
4076 KB |
Output is correct |
| 28 |
Correct |
44 ms |
7080 KB |
Output is correct |
| 29 |
Correct |
45 ms |
7000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
544 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1364 KB |
Output is correct |
| 5 |
Correct |
28 ms |
5076 KB |
Output is correct |
| 6 |
Correct |
25 ms |
5076 KB |
Output is correct |
| 7 |
Correct |
24 ms |
4692 KB |
Output is correct |
| 8 |
Correct |
27 ms |
5092 KB |
Output is correct |
| 9 |
Correct |
27 ms |
5100 KB |
Output is correct |
| 10 |
Correct |
27 ms |
5060 KB |
Output is correct |
| 11 |
Correct |
26 ms |
5120 KB |
Output is correct |
| 12 |
Correct |
30 ms |
5008 KB |
Output is correct |
| 13 |
Correct |
31 ms |
4948 KB |
Output is correct |
| 14 |
Correct |
26 ms |
4948 KB |
Output is correct |
| 15 |
Correct |
8 ms |
1364 KB |
Output is correct |
| 16 |
Correct |
15 ms |
2564 KB |
Output is correct |
| 17 |
Correct |
154 ms |
80960 KB |
Output is correct |
| 18 |
Correct |
167 ms |
81596 KB |
Output is correct |
| 19 |
Correct |
177 ms |
81100 KB |
Output is correct |
| 20 |
Correct |
161 ms |
81140 KB |
Output is correct |
| 21 |
Correct |
161 ms |
83404 KB |
Output is correct |
| 22 |
Correct |
176 ms |
82732 KB |
Output is correct |
| 23 |
Correct |
161 ms |
81520 KB |
Output is correct |
| 24 |
Correct |
155 ms |
82000 KB |
Output is correct |
| 25 |
Correct |
172 ms |
80832 KB |
Output is correct |
| 26 |
Correct |
157 ms |
81868 KB |
Output is correct |
| 27 |
Correct |
24 ms |
4076 KB |
Output is correct |
| 28 |
Correct |
44 ms |
7080 KB |
Output is correct |
| 29 |
Correct |
45 ms |
7000 KB |
Output is correct |
| 30 |
Runtime error |
3416 ms |
1048576 KB |
Execution killed with signal 9 |
| 31 |
Halted |
0 ms |
0 KB |
- |
