Submission #724998

#	Time	Username	Problem	Language	Result	Execution time	Memory
724998		finn__	Dancing Elephants (IOI11_elephants)	C++17	100 / 100	3486 ms	12460 KiB

elephants

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

#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;

constexpr size_t MAX_N = 151000, B = 387;
int l;

struct Bucket
{
    size_t n;
    int x[2 * B], k[2 * B], o[2 * B];

    void build(size_t m) // Recalculate the first m elephants.
    {
        size_t i = m - 1, j = upper_bound(x, x + n, x[i] + l) - x;
        while (i < m)
        {
            while (j > i + 1 && x[i] + l < x[j - 1])
                --j;
            if (j == n)
                k[i] = 1, o[i] = x[i] + l;
            else
                k[i] = k[j] + 1, o[i] = o[j];
            --i;
        }
    }

    void insert(int y)
    {
        x[n] = y;
        size_t i = n;
        while (i && x[i] < x[i - 1])
            swap(x[i], x[i - 1]), swap(k[i], k[i - 1]), swap(o[i], o[i - 1]), --i;
        ++n;
        build(i + 1);
    }

    void erase(size_t i)
    {
        for (size_t j = i; j < n - 1; ++j)
            swap(x[j], x[j + 1]), swap(k[j], k[j + 1]), swap(o[j], o[j + 1]);
        --n;
        if (i)
            build(i);
    }
};

size_t iteration_count = 0;
Bucket b[MAX_N / B];
int u[MAX_N], v[MAX_N];

void init(int N, int L, int X[])
{
    l = L;
    for (size_t i = 0; i <= N / B; ++i)
    {
        for (size_t j = 0; j < B && i * B + j < N; ++j)
            b[i].x[j] = X[i * B + j], ++b[i].n;
        b[i].build(b[i].n);
    }
    memcpy(u, X, N * sizeof *X);
}

int update(int i, int y)
{
    if (iteration_count == B - 1)
    {
        size_t k = 0;
        for (size_t i = 0; i < MAX_N / B; ++i)
        {
            for (size_t j = 0; j < b[i].n; ++j)
                v[k++] = b[i].x[j];
            b[i].n = 0;
        }
        for (size_t i = 0; i <= k / B; ++i)
        {
            for (size_t j = 0; j < B && i * B + j < k; ++j)
                b[i].x[j] = v[i * B + j], ++b[i].n;
            b[i].build(b[i].n);
        }
        iteration_count = 0;
    }

    ++iteration_count;
    for (size_t j = 0;; ++j)
        if (b[j].x[0] <= u[i] && u[i] <= b[j].x[b[j].n - 1])
        {
            b[j].erase(lower_bound(b[j].x, b[j].x + b[j].n, u[i]) - b[j].x);
            break;
        }
    u[i] = y;
    for (size_t j = 0;; ++j)
        if ((!j || b[j].x[0] <= y) && (!b[j + 1].n || y <= b[j + 1].x[0]))
        {
            b[j].insert(y);
            break;
        }

    int covered = -1, cameras = 0;
    for (size_t j = 0; b[j].n; ++j)
        if (b[j].x[b[j].n - 1] > covered)
        {
            size_t const k = upper_bound(b[j].x, b[j].x + b[j].n, covered) - b[j].x;
            covered = b[j].o[k];
            cameras += b[j].k[k];
        }
    return cameras;
}

Compilation message (stderr)

elephants.cpp: In function 'void init(int, int, int*)':
elephants.cpp:60:47: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |         for (size_t j = 0; j < B && i * B + j < N; ++j)
      |                                     ~~~~~~~~~~^~~

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3