답안 #723194

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
723194 2023-04-13T10:11:02 Z finn__ Golf (JOI17_golf) C++17
30 / 100
10000 ms 861852 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 */
};

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->a;
                node->l->b = (node->a + node->b) / 2;
            }
            else if ((node->l->b - node->l->a + 1) * 2 != (node->b - node->a + 1))
            {
                NodeY *z = (NodeY *)calloc(1, sizeof *node->l);
                z->a = node->a;
                z->b = (node->a + node->b) / 2;
                if (node->l->b <= (z->a + z->b) / 2)
                    z->l = node->l;
                else
                    z->r = node->l;
                node->l = z;
            }
            insertIntervalY(node->l, k, x);
        }
        else
        {
            if (!node->r)
            {
                node->r = (NodeY *)calloc(1, sizeof *node->r);
                node->r->a = (node->a + node->b) / 2 + 1;
                node->r->b = node->b;
            }
            else if ((node->r->b - node->r->a + 1) * 2 != (node->b - node->a + 1))
            {
                NodeY *z = (NodeY *)calloc(1, sizeof *node->r);
                z->a = (node->a + node->b) / 2 + 1;
                z->b = node->b;
                if (node->r->b <= (z->a + z->b) / 2)
                    z->l = node->r;
                else
                    z->r = node->r;
                node->r = z;
            }
            insertIntervalY(node->r, k, x);
        }
        if (node->l && (!node->l->l ^ !node->l->r))
        {
            NodeY *z = node->l->l ? node->l->l : node->l->r;
            free(node->l);
            node->l = z;
        }
        if (node->r && (!node->r->l ^ !node->r->r))
        {
            NodeY *z = node->r->l ? node->r->l : node->r->r;
            free(node->r);
            node->r = z;
        }
        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);
    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.cpp: In function 'int main()':
golf.cpp:269:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  269 |     scanf("%d %d %d %d %zu", &S, &T, &U, &V, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:273:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  273 |         scanf("%d %d %d %d", r[i], r[i] + 1, r[i] + 2, r[i] + 3);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 5 ms 592 KB Output is correct
5 Correct 38 ms 2264 KB Output is correct
6 Correct 36 ms 2276 KB Output is correct
7 Correct 36 ms 2080 KB Output is correct
8 Correct 45 ms 2244 KB Output is correct
9 Correct 42 ms 2332 KB Output is correct
10 Correct 41 ms 2200 KB Output is correct
11 Correct 44 ms 2312 KB Output is correct
12 Correct 41 ms 2196 KB Output is correct
13 Correct 37 ms 2148 KB Output is correct
14 Correct 39 ms 2124 KB Output is correct
15 Correct 20 ms 972 KB Output is correct
16 Correct 39 ms 1696 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 5 ms 592 KB Output is correct
5 Correct 38 ms 2264 KB Output is correct
6 Correct 36 ms 2276 KB Output is correct
7 Correct 36 ms 2080 KB Output is correct
8 Correct 45 ms 2244 KB Output is correct
9 Correct 42 ms 2332 KB Output is correct
10 Correct 41 ms 2200 KB Output is correct
11 Correct 44 ms 2312 KB Output is correct
12 Correct 41 ms 2196 KB Output is correct
13 Correct 37 ms 2148 KB Output is correct
14 Correct 39 ms 2124 KB Output is correct
15 Correct 20 ms 972 KB Output is correct
16 Correct 39 ms 1696 KB Output is correct
17 Correct 146 ms 13448 KB Output is correct
18 Correct 146 ms 13512 KB Output is correct
19 Correct 137 ms 13516 KB Output is correct
20 Correct 171 ms 13488 KB Output is correct
21 Correct 196 ms 13708 KB Output is correct
22 Correct 141 ms 13608 KB Output is correct
23 Correct 141 ms 13648 KB Output is correct
24 Correct 149 ms 13596 KB Output is correct
25 Correct 132 ms 13452 KB Output is correct
26 Correct 138 ms 13668 KB Output is correct
27 Correct 77 ms 3904 KB Output is correct
28 Correct 144 ms 7152 KB Output is correct
29 Correct 139 ms 7080 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 5 ms 592 KB Output is correct
5 Correct 38 ms 2264 KB Output is correct
6 Correct 36 ms 2276 KB Output is correct
7 Correct 36 ms 2080 KB Output is correct
8 Correct 45 ms 2244 KB Output is correct
9 Correct 42 ms 2332 KB Output is correct
10 Correct 41 ms 2200 KB Output is correct
11 Correct 44 ms 2312 KB Output is correct
12 Correct 41 ms 2196 KB Output is correct
13 Correct 37 ms 2148 KB Output is correct
14 Correct 39 ms 2124 KB Output is correct
15 Correct 20 ms 972 KB Output is correct
16 Correct 39 ms 1696 KB Output is correct
17 Correct 146 ms 13448 KB Output is correct
18 Correct 146 ms 13512 KB Output is correct
19 Correct 137 ms 13516 KB Output is correct
20 Correct 171 ms 13488 KB Output is correct
21 Correct 196 ms 13708 KB Output is correct
22 Correct 141 ms 13608 KB Output is correct
23 Correct 141 ms 13648 KB Output is correct
24 Correct 149 ms 13596 KB Output is correct
25 Correct 132 ms 13452 KB Output is correct
26 Correct 138 ms 13668 KB Output is correct
27 Correct 77 ms 3904 KB Output is correct
28 Correct 144 ms 7152 KB Output is correct
29 Correct 139 ms 7080 KB Output is correct
30 Execution timed out 10057 ms 861852 KB Time limit exceeded
31 Halted 0 ms 0 KB -