Submission #723116

#	Time	Username	Problem	Language	Result	Execution time	Memory
723116		finn__	Golf (JOI17_golf)	C++17	30 / 100	3416 ms	1048576 KiB

golf

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <stdint.h>
#include <stdbool.h>

#define N 100009
#define X (1LL << 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;
    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 (b < i || a > j)
        return;
    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 (!node->l)
            node->l = (NodeX *)calloc(1, sizeof *node->l);
        if (!node->r)
            node->r = (NodeX *)calloc(1, sizeof *node->r);
        insertIntervalX(node->l, i, j, k, x, a, (a + b) / 2);
        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 (b < i || a > j)
        return;
    if (i <= a && b <= j)
        removeIntervalY(node->y, k, 0, X - 1);
    else
    {
        removeIntervalX(node->l, i, j, k, a, (a + b) / 2);
        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];
size_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 (stderr)

golf.cpp: In function 'int main()':
golf.cpp:221:15: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'L*' {aka 'int*'} [-Wformat=]
  221 |     scanf("%lld %lld %lld %lld %zu", &S, &T, &U, &V, &n);
      |            ~~~^                      ~~
      |               |                      |
      |               long long int*         L* {aka int*}
      |            %d
golf.cpp:221:20: warning: format '%lld' expects argument of type 'long long int*', but argument 3 has type 'L*' {aka 'int*'} [-Wformat=]
  221 |     scanf("%lld %lld %lld %lld %zu", &S, &T, &U, &V, &n);
      |                 ~~~^                     ~~
      |                    |                     |
      |                    long long int*        L* {aka int*}
      |                 %d
golf.cpp:221:25: warning: format '%lld' expects argument of type 'long long int*', but argument 4 has type 'L*' {aka 'int*'} [-Wformat=]
  221 |     scanf("%lld %lld %lld %lld %zu", &S, &T, &U, &V, &n);
      |                      ~~~^                    ~~
      |                         |                    |
      |                         long long int*       L* {aka int*}
      |                      %d
golf.cpp:221:30: warning: format '%lld' expects argument of type 'long long int*', but argument 5 has type 'L*' {aka 'int*'} [-Wformat=]
  221 |     scanf("%lld %lld %lld %lld %zu", &S, &T, &U, &V, &n);
      |                           ~~~^                   ~~
      |                              |                   |
      |                              long long int*      L* {aka int*}
      |                           %d
golf.cpp:224:19: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'L*' {aka 'int*'} [-Wformat=]
  224 |         scanf("%lld %lld %lld %lld", r[i], r[i] + 1, r[i] + 2, r[i] + 3);
      |                ~~~^                  ~~~~
      |                   |                     |
      |                   long long int*        L* {aka int*}
      |                %d
golf.cpp:224:24: warning: format '%lld' expects argument of type 'long long int*', but argument 3 has type 'L*' {aka 'int*'} [-Wformat=]
  224 |         scanf("%lld %lld %lld %lld", r[i], r[i] + 1, r[i] + 2, r[i] + 3);
      |                     ~~~^                   ~~~~~~~~
      |                        |                        |
      |                        long long int*           L* {aka int*}
      |                     %d
golf.cpp:224:29: warning: format '%lld' expects argument of type 'long long int*', but argument 4 has type 'L*' {aka 'int*'} [-Wformat=]
  224 |         scanf("%lld %lld %lld %lld", r[i], r[i] + 1, r[i] + 2, r[i] + 3);
      |                          ~~~^                        ~~~~~~~~
      |                             |                             |
      |                             long long int*                L* {aka int*}
      |                          %d
golf.cpp:224:34: warning: format '%lld' expects argument of type 'long long int*', but argument 5 has type 'L*' {aka 'int*'} [-Wformat=]
  224 |         scanf("%lld %lld %lld %lld", r[i], r[i] + 1, r[i] + 2, r[i] + 3);
      |                               ~~~^                             ~~~~~~~~
      |                                  |                                  |
      |                                  long long int*                     L* {aka int*}
      |                               %d
golf.cpp:221:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  221 |     scanf("%lld %lld %lld %lld %zu", &S, &T, &U, &V, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:224:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  224 |         scanf("%lld %lld %lld %lld", r[i], r[i] + 1, r[i] + 2, r[i] + 3);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 70