답안 #723202

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
723202 2023-04-13T10:36:17 Z finn__ Golf (JOI17_golf) C
100 / 100
6621 ms 973968 KB
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <stdint.h>
#include <inttypes.h>
#include <stdbool.h>

#define N 100009
#define X (1 << 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;
    L a, b;
    size_t x; /* interval count in internal nodes, index in leaf nodes */
};

NodeY *insertInBetween(NodeY *node, L k, L a, L b)
{
    NodeY *z = (NodeY *)calloc(1, sizeof *z);
    z->a = a, z->b = b;
    while (1)
    {
        L const mid = (z->a + z->b) / 2;
        if (node->b <= mid && k <= mid)
            z->b = mid;
        else if (node->a > mid && k > mid)
            z->a = mid + 1;
        else
            break;
    }
    if (node->b <= (z->a + z->b) / 2)
        z->l = node;
    else
        z->r = node;
    return z;
}

void insertIntervalY(NodeY *node, L k, size_t x)
{
    if (node->a == node->b)
    {
        if (!node->x)
            node->x = x + 1; /* + 1, since 0 signifies there is no interval */
    }
    else
    {
        if (k <= (node->a + node->b) / 2)
        {
            if (!node->l)
            {
                node->l = (NodeY *)calloc(1, sizeof *node->l);
                node->l->a = node->l->b = k;
            }
            else if (!(node->l->a <= k && k <= node->l->b))
                node->l = insertInBetween(node->l, k, node->a, (node->a + node->b) / 2);
            insertIntervalY(node->l, k, x);
        }
        else
        {
            if (!node->r)
            {
                node->r = (NodeY *)calloc(1, sizeof *node->r);
                node->r->a = node->r->b = k;
            }
            else if (!(node->r->a <= k && k <= node->r->b))
                node->r = insertInBetween(node->r, k, (node->a + node->b + 1) / 2, node->b);
            insertIntervalY(node->r, k, x);
        }
        node->x = (node->l ? (node->l->a == node->l->b ? (bool)node->l->x : node->l->x) : 0) +
                  (node->r ? (node->r->a == node->r->b ? (bool)node->r->x : node->r->x) : 0);
    }
}

size_t getNextIntervalY(NodeY *node, L i, L j)
{
    if (node->b < i || node->a > j)
        return SIZE_MAX;
    if (i <= node->a && node->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);
        if (x == SIZE_MAX && node->r)
            x = getNextIntervalY(node->r, i, j);
        return x;
    }
}

void removeIntervalY(NodeY *node, L k)
{
    if (node->a == node->b)
        node->x = 0;
    else
    {
        --node->x;
        if (k <= (node->a + node->b) / 2)
            removeIntervalY(node->l, k);
        else
            removeIntervalY(node->r, k);
    }
}

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 (i <= a && b <= j)
    {
        if (!node->y)
        {
            node->y = (NodeY *)calloc(1, sizeof *node->y);
            node->y->a = 0;
            node->y->b = X - 1;
        }
        insertIntervalY(node->y, k, x);
    }
    else
    {
        if (i <= (a + b) / 2)
        {
            if (!node->l)
                node->l = (NodeX *)calloc(1, sizeof *node->l);
            insertIntervalX(node->l, i, j, k, x, a, (a + b) / 2);
        }
        if (j >= (a + b) / 2 + 1)
        {
            if (!node->r)
                node->r = (NodeX *)calloc(1, sizeof *node->r);
            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) : 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 (i <= a && b <= j)
        removeIntervalY(node->y, k);
    else
    {
        if (i <= (a + b) / 2)
            removeIntervalX(node->l, i, j, k, a, (a + b) / 2);
        if (j >= (a + b) / 2 + 1)
            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)[4], t[4 * N][2];
uint32_t queue[4 * N], distance[4 * N];
Node root;
NodeX horizontal, vertical;

int main()
{
    L S, T, U, V;
    size_t n;
    scanf("%d %d %d %d %zu", &S, &T, &U, &V, &n);
    s = (L(*)[4])malloc(N * sizeof *s);
    for (size_t i = 0; i < n; i++)
    {
        scanf("%d %d %d %d", 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;
    }

    free(s);
    reset(&root);
    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;
            if (v == 4 * (n - 1) || v == 4 * (n - 1) + 2)
            {
                printf("%" PRIu32 "\n", distance[v]);
                return 0;
            }
            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);
        }
    }
}

Compilation message

golf.c: In function 'main':
golf.c:258:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  258 |     scanf("%d %d %d %d %zu", &S, &T, &U, &V, &n);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.c:262:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  262 |         scanf("%d %d %d %d", r[i], r[i] + 1, r[i] + 2, r[i] + 3);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 14 ms 2380 KB Output is correct
6 Correct 10 ms 2244 KB Output is correct
7 Correct 11 ms 2020 KB Output is correct
8 Correct 11 ms 2140 KB Output is correct
9 Correct 11 ms 2236 KB Output is correct
10 Correct 10 ms 2152 KB Output is correct
11 Correct 15 ms 2244 KB Output is correct
12 Correct 11 ms 2256 KB Output is correct
13 Correct 12 ms 2112 KB Output is correct
14 Correct 14 ms 2160 KB Output is correct
15 Correct 6 ms 972 KB Output is correct
16 Correct 10 ms 1732 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 14 ms 2380 KB Output is correct
6 Correct 10 ms 2244 KB Output is correct
7 Correct 11 ms 2020 KB Output is correct
8 Correct 11 ms 2140 KB Output is correct
9 Correct 11 ms 2236 KB Output is correct
10 Correct 10 ms 2152 KB Output is correct
11 Correct 15 ms 2244 KB Output is correct
12 Correct 11 ms 2256 KB Output is correct
13 Correct 12 ms 2112 KB Output is correct
14 Correct 14 ms 2160 KB Output is correct
15 Correct 6 ms 972 KB Output is correct
16 Correct 10 ms 1732 KB Output is correct
17 Correct 37 ms 11272 KB Output is correct
18 Correct 35 ms 11332 KB Output is correct
19 Correct 38 ms 11364 KB Output is correct
20 Correct 39 ms 11324 KB Output is correct
21 Correct 40 ms 11440 KB Output is correct
22 Correct 34 ms 11512 KB Output is correct
23 Correct 41 ms 11412 KB Output is correct
24 Correct 42 ms 11432 KB Output is correct
25 Correct 36 ms 11324 KB Output is correct
26 Correct 38 ms 11460 KB Output is correct
27 Correct 13 ms 3916 KB Output is correct
28 Correct 25 ms 7140 KB Output is correct
29 Correct 24 ms 7004 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 14 ms 2380 KB Output is correct
6 Correct 10 ms 2244 KB Output is correct
7 Correct 11 ms 2020 KB Output is correct
8 Correct 11 ms 2140 KB Output is correct
9 Correct 11 ms 2236 KB Output is correct
10 Correct 10 ms 2152 KB Output is correct
11 Correct 15 ms 2244 KB Output is correct
12 Correct 11 ms 2256 KB Output is correct
13 Correct 12 ms 2112 KB Output is correct
14 Correct 14 ms 2160 KB Output is correct
15 Correct 6 ms 972 KB Output is correct
16 Correct 10 ms 1732 KB Output is correct
17 Correct 37 ms 11272 KB Output is correct
18 Correct 35 ms 11332 KB Output is correct
19 Correct 38 ms 11364 KB Output is correct
20 Correct 39 ms 11324 KB Output is correct
21 Correct 40 ms 11440 KB Output is correct
22 Correct 34 ms 11512 KB Output is correct
23 Correct 41 ms 11412 KB Output is correct
24 Correct 42 ms 11432 KB Output is correct
25 Correct 36 ms 11324 KB Output is correct
26 Correct 38 ms 11460 KB Output is correct
27 Correct 13 ms 3916 KB Output is correct
28 Correct 25 ms 7140 KB Output is correct
29 Correct 24 ms 7004 KB Output is correct
30 Correct 4674 ms 948004 KB Output is correct
31 Correct 5354 ms 951736 KB Output is correct
32 Correct 5894 ms 945940 KB Output is correct
33 Correct 6510 ms 953416 KB Output is correct
34 Correct 5160 ms 973968 KB Output is correct
35 Correct 6621 ms 968952 KB Output is correct
36 Correct 4555 ms 960080 KB Output is correct
37 Correct 5801 ms 950548 KB Output is correct
38 Correct 5393 ms 968416 KB Output is correct
39 Correct 5924 ms 953008 KB Output is correct
40 Correct 387 ms 44276 KB Output is correct
41 Correct 354 ms 43736 KB Output is correct
42 Correct 357 ms 44184 KB Output is correct
43 Correct 389 ms 44444 KB Output is correct
44 Correct 411 ms 44820 KB Output is correct
45 Correct 425 ms 45240 KB Output is correct
46 Correct 416 ms 45092 KB Output is correct
47 Correct 393 ms 44444 KB Output is correct
48 Correct 360 ms 44816 KB Output is correct
49 Correct 344 ms 44420 KB Output is correct
50 Correct 19 ms 6596 KB Output is correct
51 Correct 20 ms 6944 KB Output is correct
52 Correct 22 ms 6980 KB Output is correct