답안 #723116

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
723116 2023-04-13T08:54:09 Z finn__ Golf (JOI17_golf) C++17
30 / 100
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);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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 -