답안 #723184

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
723184	2023-04-13T10:06:44 Z	finn__	Golf (JOI17_golf)	C++17	30 / 100	10000 ms	837252 KB

golf

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2")

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <stdint.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;
            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:271:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  271 |     scanf("%d %d %d %d %zu", &S, &T, &U, &V, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:275:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  275 |         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	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	656 KB	Output is correct
5	Correct	33 ms	2240 KB	Output is correct
6	Correct	34 ms	2300 KB	Output is correct
7	Correct	33 ms	2056 KB	Output is correct
8	Correct	33 ms	2292 KB	Output is correct
9	Correct	35 ms	2372 KB	Output is correct
10	Correct	32 ms	2224 KB	Output is correct
11	Correct	35 ms	2276 KB	Output is correct
12	Correct	36 ms	2268 KB	Output is correct
13	Correct	34 ms	2188 KB	Output is correct
14	Correct	34 ms	2244 KB	Output is correct
15	Correct	17 ms	1080 KB	Output is correct
16	Correct	39 ms	1768 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	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	656 KB	Output is correct
5	Correct	33 ms	2240 KB	Output is correct
6	Correct	34 ms	2300 KB	Output is correct
7	Correct	33 ms	2056 KB	Output is correct
8	Correct	33 ms	2292 KB	Output is correct
9	Correct	35 ms	2372 KB	Output is correct
10	Correct	32 ms	2224 KB	Output is correct
11	Correct	35 ms	2276 KB	Output is correct
12	Correct	36 ms	2268 KB	Output is correct
13	Correct	34 ms	2188 KB	Output is correct
14	Correct	34 ms	2244 KB	Output is correct
15	Correct	17 ms	1080 KB	Output is correct
16	Correct	39 ms	1768 KB	Output is correct
17	Correct	145 ms	13456 KB	Output is correct
18	Correct	151 ms	13544 KB	Output is correct
19	Correct	147 ms	13476 KB	Output is correct
20	Correct	142 ms	13492 KB	Output is correct
21	Correct	145 ms	13788 KB	Output is correct
22	Correct	138 ms	13608 KB	Output is correct
23	Correct	144 ms	13656 KB	Output is correct
24	Correct	148 ms	13600 KB	Output is correct
25	Correct	158 ms	13480 KB	Output is correct
26	Correct	146 ms	13568 KB	Output is correct
27	Correct	74 ms	3976 KB	Output is correct
28	Correct	136 ms	7088 KB	Output is correct
29	Correct	157 ms	7004 KB	Output is correct

Subtask #3

0 / 70.0

#	결과	실행 시간	메모리	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	656 KB	Output is correct
5	Correct	33 ms	2240 KB	Output is correct
6	Correct	34 ms	2300 KB	Output is correct
7	Correct	33 ms	2056 KB	Output is correct
8	Correct	33 ms	2292 KB	Output is correct
9	Correct	35 ms	2372 KB	Output is correct
10	Correct	32 ms	2224 KB	Output is correct
11	Correct	35 ms	2276 KB	Output is correct
12	Correct	36 ms	2268 KB	Output is correct
13	Correct	34 ms	2188 KB	Output is correct
14	Correct	34 ms	2244 KB	Output is correct
15	Correct	17 ms	1080 KB	Output is correct
16	Correct	39 ms	1768 KB	Output is correct
17	Correct	145 ms	13456 KB	Output is correct
18	Correct	151 ms	13544 KB	Output is correct
19	Correct	147 ms	13476 KB	Output is correct
20	Correct	142 ms	13492 KB	Output is correct
21	Correct	145 ms	13788 KB	Output is correct
22	Correct	138 ms	13608 KB	Output is correct
23	Correct	144 ms	13656 KB	Output is correct
24	Correct	148 ms	13600 KB	Output is correct
25	Correct	158 ms	13480 KB	Output is correct
26	Correct	146 ms	13568 KB	Output is correct
27	Correct	74 ms	3976 KB	Output is correct
28	Correct	136 ms	7088 KB	Output is correct
29	Correct	157 ms	7004 KB	Output is correct
30	Execution timed out	10109 ms	837252 KB	Time limit exceeded
31	Halted	0 ms	0 KB	-