oj.uz

답안 #723165

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
723165 2023-04-13T09:56:08 Z finn__ Golf (JOI17_golf) C++17
10 / 100
 68 ms 55912 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 1000000
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);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 23760 KB Output is correct
2 Correct 10 ms 23760 KB Output is correct
3 Correct 11 ms 23808 KB Output is correct
4 Correct 13 ms 23744 KB Output is correct
5 Correct 31 ms 24016 KB Output is correct
6 Correct 33 ms 23988 KB Output is correct
7 Correct 33 ms 23968 KB Output is correct
8 Correct 34 ms 23984 KB Output is correct
9 Correct 33 ms 23980 KB Output is correct
10 Correct 32 ms 23948 KB Output is correct
11 Correct 33 ms 23996 KB Output is correct
12 Correct 32 ms 23992 KB Output is correct
13 Correct 31 ms 23968 KB Output is correct
14 Correct 32 ms 24012 KB Output is correct
15 Correct 17 ms 23856 KB Output is correct
16 Correct 26 ms 23920 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 23760 KB Output is correct
2 Correct 10 ms 23760 KB Output is correct
3 Correct 11 ms 23808 KB Output is correct
4 Correct 13 ms 23744 KB Output is correct
5 Correct 31 ms 24016 KB Output is correct
6 Correct 33 ms 23988 KB Output is correct
7 Correct 33 ms 23968 KB Output is correct
8 Correct 34 ms 23984 KB Output is correct
9 Correct 33 ms 23980 KB Output is correct
10 Correct 32 ms 23948 KB Output is correct
11 Correct 33 ms 23996 KB Output is correct
12 Correct 32 ms 23992 KB Output is correct
13 Correct 31 ms 23968 KB Output is correct
14 Correct 32 ms 24012 KB Output is correct
15 Correct 17 ms 23856 KB Output is correct
16 Correct 26 ms 23920 KB Output is correct
17 Runtime error 68 ms 55912 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 23760 KB Output is correct
2 Correct 10 ms 23760 KB Output is correct
3 Correct 11 ms 23808 KB Output is correct
4 Correct 13 ms 23744 KB Output is correct
5 Correct 31 ms 24016 KB Output is correct
6 Correct 33 ms 23988 KB Output is correct
7 Correct 33 ms 23968 KB Output is correct
8 Correct 34 ms 23984 KB Output is correct
9 Correct 33 ms 23980 KB Output is correct
10 Correct 32 ms 23948 KB Output is correct
11 Correct 33 ms 23996 KB Output is correct
12 Correct 32 ms 23992 KB Output is correct
13 Correct 31 ms 23968 KB Output is correct
14 Correct 32 ms 24012 KB Output is correct
15 Correct 17 ms 23856 KB Output is correct
16 Correct 26 ms 23920 KB Output is correct
17 Runtime error 68 ms 55912 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -