답안 #723171

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
723171 2023-04-13T09:57:47 Z finn__ Golf (JOI17_golf) C++17
30 / 100
3647 ms 959124 KB
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <stdint.h>
#include <stdbool.h>

#define N 100009
#define X (1LL << 30)
#define MAX_Y_NODES 15000000
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
{
    uint32_t l, r;
    uint32_t x; /* interval count in internal nodes, index in leaf nodes */
};

size_t yIndex[2];
NodeY yNodes[2][MAX_Y_NODES];

bool insertIntervalY(uint32_t I, NodeY *node, L k, uint32_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 == UINT32_MAX)
                node->l = yIndex[I]++;
            bool inserted = insertIntervalY(I, yNodes[I] + node->l, k, x, a, (a + b) / 2);
            node->x += inserted;
            return inserted;
        }
        else
        {
            if (node->r == UINT32_MAX)
                node->r = yIndex[I]++;
            bool inserted = insertIntervalY(I, yNodes[I] + node->r, k, x, (a + b) / 2 + 1, b);
            node->x += inserted;
            return inserted;
        }
    }
}

uint32_t getNextIntervalY(uint32_t I, NodeY *node, L i, L j, L a, L b)
{
    if (b < i || a > j)
        return UINT32_MAX;
    if (i <= a && b <= j)
    {
        if (!node->x)
            return UINT32_MAX;
        while (node->l != UINT32_MAX || node->r != UINT32_MAX)
            node = (node->l != UINT32_MAX && (yNodes[I] + node->l)->x)
                       ? yNodes[I] + node->l
                       : yNodes[I] + node->r;
        return node->x - 1;
    }
    else
    {
        size_t x = UINT32_MAX;
        if (node->l != UINT32_MAX)
            x = getNextIntervalY(I, yNodes[I] + node->l, i, j, a, (a + b) / 2);
        if (x == UINT32_MAX && node->r != UINT32_MAX)
            x = getNextIntervalY(I, yNodes[I] + node->r, i, j, (a + b) / 2 + 1, b);
        return x;
    }
}

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

typedef struct NodeX NodeX;
struct NodeX
{
    NodeX *l, *r;
    NodeY *y;
};

void insertIntervalX(uint32_t I, NodeX *node, L i, L j, L k, uint32_t x, L a, L b)
{
    if (i <= a && b <= j)
    {
        if (!node->y)
            node->y = yNodes[I] + yIndex[I]++;
        insertIntervalY(I, node->y, k, x, 0, X - 1);
    }
    else
    {
        if (i <= (a + b) / 2)
        {
            if (!node->l)
                node->l = (NodeX *)calloc(1, sizeof *node->l);
            insertIntervalX(I, 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(I, node->r, i, j, k, x, (a + b) / 2 + 1, b);
        }
    }
}

uint32_t getNextIntervalX(uint32_t I, NodeX *node, L i, L j, L k, L a, L b)
{
    uint32_t x = node->y ? getNextIntervalY(I, node->y, i, j, 0, X - 1) : UINT32_MAX;
    if (x != UINT32_MAX || a == b)
        return x;
    if (k <= (a + b) / 2)
        return node->l ? getNextIntervalX(I, node->l, i, j, k, a, (a + b) / 2) : UINT32_MAX;
    return node->r ? getNextIntervalX(I, node->r, i, j, k, (a + b) / 2 + 1, b) : UINT32_MAX;
}

void removeIntervalX(uint32_t I, NodeX *node, L i, L j, L k, L a, L b)
{
    if (i <= a && b <= j)
        removeIntervalY(I, node->y, k, 0, X - 1);
    else
    {
        if (i <= (a + b) / 2)
            removeIntervalX(I, node->l, i, j, k, a, (a + b) / 2);
        if (j >= (a + b) / 2 + 1)
            removeIntervalX(I, 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);
    for (size_t i = 0; i < MAX_Y_NODES; i++)
        yNodes[0][i].l = yNodes[0][i].r = yNodes[1][i].l = yNodes[1][i].r = UINT32_MAX;

    insertIntervalX(0, &horizontal, t[4 * (n - 1)][0], t[4 * (n - 1)][1],
                    V, 4 * (n - 1), 0, X - 1);
    insertIntervalX(1, &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(0, &horizontal, t[i][0], t[i][1], r[i >> 2][(i + 2) & 3], i, 0, X - 1);
        else
            insertIntervalX(1, &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)
    {
        uint32_t const u = queue[i++];
        uint32_t v = getNextIntervalX((u & 3) < 2, (u & 3) < 2 ? &vertical : &horizontal,
                                      t[u][0], t[u][1], r[u >> 2][(u + 2) & 3], 0, X - 1);
        while (v != UINT32_MAX)
        {
            distance[v] = distance[u] + 1;
            queue[j++] = v;
            removeIntervalX((v & 3) >= 2, (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, (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:231:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  231 |     scanf("%d %d %d %d %zu", &S, &T, &U, &V, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:235:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  235 |         scanf("%d %d %d %d", r[i], r[i] + 1, r[i] + 2, r[i] + 3);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 158 ms 352544 KB Output is correct
2 Correct 165 ms 352672 KB Output is correct
3 Correct 168 ms 352452 KB Output is correct
4 Correct 163 ms 352584 KB Output is correct
5 Correct 174 ms 352720 KB Output is correct
6 Correct 177 ms 352704 KB Output is correct
7 Correct 180 ms 352700 KB Output is correct
8 Correct 172 ms 352696 KB Output is correct
9 Correct 191 ms 352688 KB Output is correct
10 Correct 227 ms 352768 KB Output is correct
11 Correct 180 ms 352724 KB Output is correct
12 Correct 179 ms 352668 KB Output is correct
13 Correct 209 ms 352680 KB Output is correct
14 Correct 182 ms 352764 KB Output is correct
15 Correct 158 ms 352508 KB Output is correct
16 Correct 164 ms 352636 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 158 ms 352544 KB Output is correct
2 Correct 165 ms 352672 KB Output is correct
3 Correct 168 ms 352452 KB Output is correct
4 Correct 163 ms 352584 KB Output is correct
5 Correct 174 ms 352720 KB Output is correct
6 Correct 177 ms 352704 KB Output is correct
7 Correct 180 ms 352700 KB Output is correct
8 Correct 172 ms 352696 KB Output is correct
9 Correct 191 ms 352688 KB Output is correct
10 Correct 227 ms 352768 KB Output is correct
11 Correct 180 ms 352724 KB Output is correct
12 Correct 179 ms 352668 KB Output is correct
13 Correct 209 ms 352680 KB Output is correct
14 Correct 182 ms 352764 KB Output is correct
15 Correct 158 ms 352508 KB Output is correct
16 Correct 164 ms 352636 KB Output is correct
17 Correct 262 ms 356548 KB Output is correct
18 Correct 261 ms 356652 KB Output is correct
19 Correct 223 ms 356688 KB Output is correct
20 Correct 219 ms 356660 KB Output is correct
21 Correct 223 ms 356736 KB Output is correct
22 Correct 225 ms 356780 KB Output is correct
23 Correct 210 ms 356636 KB Output is correct
24 Correct 219 ms 356692 KB Output is correct
25 Correct 224 ms 356572 KB Output is correct
26 Correct 220 ms 356640 KB Output is correct
27 Correct 179 ms 352608 KB Output is correct
28 Correct 209 ms 352696 KB Output is correct
29 Correct 199 ms 352620 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 158 ms 352544 KB Output is correct
2 Correct 165 ms 352672 KB Output is correct
3 Correct 168 ms 352452 KB Output is correct
4 Correct 163 ms 352584 KB Output is correct
5 Correct 174 ms 352720 KB Output is correct
6 Correct 177 ms 352704 KB Output is correct
7 Correct 180 ms 352700 KB Output is correct
8 Correct 172 ms 352696 KB Output is correct
9 Correct 191 ms 352688 KB Output is correct
10 Correct 227 ms 352768 KB Output is correct
11 Correct 180 ms 352724 KB Output is correct
12 Correct 179 ms 352668 KB Output is correct
13 Correct 209 ms 352680 KB Output is correct
14 Correct 182 ms 352764 KB Output is correct
15 Correct 158 ms 352508 KB Output is correct
16 Correct 164 ms 352636 KB Output is correct
17 Correct 262 ms 356548 KB Output is correct
18 Correct 261 ms 356652 KB Output is correct
19 Correct 223 ms 356688 KB Output is correct
20 Correct 219 ms 356660 KB Output is correct
21 Correct 223 ms 356736 KB Output is correct
22 Correct 225 ms 356780 KB Output is correct
23 Correct 210 ms 356636 KB Output is correct
24 Correct 219 ms 356692 KB Output is correct
25 Correct 224 ms 356572 KB Output is correct
26 Correct 220 ms 356640 KB Output is correct
27 Correct 179 ms 352608 KB Output is correct
28 Correct 209 ms 352696 KB Output is correct
29 Correct 199 ms 352620 KB Output is correct
30 Runtime error 3647 ms 959124 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -