oj.uz

답안 #723126

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
723126 2023-04-13T09:02:10 Z finn__ Golf (JOI17_golf) C++17
30 / 100
 3358 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 long long 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 (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 (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, 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 (i <= a && b <= j)
        removeIntervalY(node->y, k, 0, X - 1);
    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[N][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("%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:225:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  225 |     scanf("%lld %lld %lld %lld %zu", &S, &T, &U, &V, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:228:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  228 |         scanf("%lld %lld %lld %lld", r[i], r[i] + 1, r[i] + 2, r[i] + 3);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 4 ms 1364 KB Output is correct
5 Correct 27 ms 5168 KB Output is correct
6 Correct 26 ms 5188 KB Output is correct
7 Correct 24 ms 4768 KB Output is correct
8 Correct 27 ms 5104 KB Output is correct
9 Correct 24 ms 5204 KB Output is correct
10 Correct 25 ms 5108 KB Output is correct
11 Correct 26 ms 5260 KB Output is correct
12 Correct 25 ms 5028 KB Output is correct
13 Correct 25 ms 5012 KB Output is correct
14 Correct 24 ms 5076 KB Output is correct
15 Correct 7 ms 1364 KB Output is correct
16 Correct 13 ms 2492 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 4 ms 1364 KB Output is correct
5 Correct 27 ms 5168 KB Output is correct
6 Correct 26 ms 5188 KB Output is correct
7 Correct 24 ms 4768 KB Output is correct
8 Correct 27 ms 5104 KB Output is correct
9 Correct 24 ms 5204 KB Output is correct
10 Correct 25 ms 5108 KB Output is correct
11 Correct 26 ms 5260 KB Output is correct
12 Correct 25 ms 5028 KB Output is correct
13 Correct 25 ms 5012 KB Output is correct
14 Correct 24 ms 5076 KB Output is correct
15 Correct 7 ms 1364 KB Output is correct
16 Correct 13 ms 2492 KB Output is correct
17 Correct 150 ms 81524 KB Output is correct
18 Correct 184 ms 82088 KB Output is correct
19 Correct 154 ms 81584 KB Output is correct
20 Correct 148 ms 81632 KB Output is correct
21 Correct 162 ms 83888 KB Output is correct
22 Correct 169 ms 83296 KB Output is correct
23 Correct 157 ms 82220 KB Output is correct
24 Correct 150 ms 82380 KB Output is correct
25 Correct 150 ms 81368 KB Output is correct
26 Correct 151 ms 82380 KB Output is correct
27 Correct 25 ms 4080 KB Output is correct
28 Correct 42 ms 7156 KB Output is correct
29 Correct 42 ms 7032 KB Output is correct

Subtask #3
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 4 ms 1364 KB Output is correct
5 Correct 27 ms 5168 KB Output is correct
6 Correct 26 ms 5188 KB Output is correct
7 Correct 24 ms 4768 KB Output is correct
8 Correct 27 ms 5104 KB Output is correct
9 Correct 24 ms 5204 KB Output is correct
10 Correct 25 ms 5108 KB Output is correct
11 Correct 26 ms 5260 KB Output is correct
12 Correct 25 ms 5028 KB Output is correct
13 Correct 25 ms 5012 KB Output is correct
14 Correct 24 ms 5076 KB Output is correct
15 Correct 7 ms 1364 KB Output is correct
16 Correct 13 ms 2492 KB Output is correct
17 Correct 150 ms 81524 KB Output is correct
18 Correct 184 ms 82088 KB Output is correct
19 Correct 154 ms 81584 KB Output is correct
20 Correct 148 ms 81632 KB Output is correct
21 Correct 162 ms 83888 KB Output is correct
22 Correct 169 ms 83296 KB Output is correct
23 Correct 157 ms 82220 KB Output is correct
24 Correct 150 ms 82380 KB Output is correct
25 Correct 150 ms 81368 KB Output is correct
26 Correct 151 ms 82380 KB Output is correct
27 Correct 25 ms 4080 KB Output is correct
28 Correct 42 ms 7156 KB Output is correct
29 Correct 42 ms 7032 KB Output is correct
30 Runtime error 3358 ms 1048576 KB Execution killed with signal 9
31 Halted 0 ms 0 KB -