Submission #645692

#	Time	Username	Problem	Language	Result	Execution time	Memory
645692		pls33	Dancing Elephants (IOI11_elephants)	C++17	100 / 100	7739 ms	17516 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;

using pf32 = pair<float, float>;
using pf64 = pair<double, double>;
using pf80 = pair<long double, long double>;
using vf32 = vector<float>;
using vf64 = vector<double>;
using vf80 = vector<long double>;
using vpf32 = vector<pf32>;
using vpf64 = vector<pf64>;
using vpf80 = vector<pf80>;
using vvf32 = vector<vf32>;
using vvf64 = vector<vf64>;
using vvf80 = vector<vf80>;
using vvpf32 = vector<vpf32>;
using vvpf64 = vector<vpf64>;
using vvpf80 = vector<vpf80>;

template <typename key, typename val>
using ord_map = tree<key, val, less<key>, rb_tree_tag,
                     tree_order_statistics_node_update>;

template <typename key>
using ord_set = tree<key, null_type, less<key>, rb_tree_tag,
                     tree_order_statistics_node_update>;
#pragma endregion

struct elephant_t
{
    int x;
    mutable int camera;
    mutable int end;
};

struct comp_t
{
    bool operator()(elephant_t a, elephant_t b) const
    {
        return a.x < b.x;
    }
};

class group_t
{
private:
    vector<elephant_t> v;
    comp_t comp;
    int length;

private:
    int find_place(int x)
    {
        elephant_t e = {x, 0, 0};
        auto it = lower_bound(v.begin(), v.end(), e, comp);

        return distance(v.begin(), it);
    }

public:
    group_t(int length)
    {
        this->length = length;
    }

    void fix()
    {
        if (v.empty())
        {
            return;
        }

        auto it = v.rbegin();

        it->camera = 1;
        it->end = it->x + length;
        it++;

        for (; it != v.rend(); it++)
        {
            elephant_t e = {it->x + length, 0, 0};
            auto prev = upper_bound(v.begin(), v.end(), e, comp);

            if (prev == v.end())
            {
                it->camera = 1;
                it->end = it->x + length;

                continue;
            }

            it->camera = prev->camera + 1;
            it->end = prev->end;
        }
    }

    void add(int x, bool fix_group)
    {
        v.insert(v.begin() + find_place(x), {x, 0, 0});

        if (fix_group)
        {
            fix();
        }
    }

    void remove(int x, bool fix_group)
    {
        assert(v.size());

        v.erase(v.begin() + find_place(x));

        if (fix_group)
        {
            fix();
        }
    }

    bool contains(int x)
    {
        elephant_t e = {x, 0, 0};
        return binary_search(v.begin(), v.end(), e, comp);
    }

    elephant_t first_after(int x)
    {
        elephant_t e = {x, 0, 0};
        auto it = upper_bound(v.begin(), v.end(), e, comp);

        if (it == v.end())
        {
            return {-1, 0, 0};
        }
        return *it;
    }

    void clear()
    {
        v.clear();
    }

    bool empty()
    {
        return v.empty();
    }

    decltype(v)::iterator begin()
    {
        return v.begin();
    }

    decltype(v)::iterator end()
    {
        return v.end();
    }

    decltype(v)::reverse_iterator rbegin()
    {
        return v.rbegin();
    }

    decltype(v)::reverse_iterator rend()
    {
        return v.rend();
    }
};

vector<group_t> group, old_group;
vector<int> position;
int camera_length;
int fix_size;

void fix_everything(vector<group_t> &g_old, vector<group_t> &g_new,
                    int group_size, int length)
{
    int i = 0;
    for (auto &g : g_old)
    {
        for (auto &e : g)
        {
            g_new[i / group_size].add(e.x, false);

            if ((i + 1) / group_size > i / group_size)
            {
                g_new[i / group_size].fix();
            }

            i++;
        }
        g.clear();
    }
}

int location(int x, p32 r)
{
    if (x < r.first)
    {
        return -1;
    }
    if (x >= r.first && x <= r.second)
    {
        return 0;
    }

    return 1;
}

// del paprastumo nedesiu i tuscias grupes...
int find_insertion(int x, vector<group_t> &group)
{
    int last = -1;
    for (size_t i = 0; i < group.size(); i++)
    {
        if (group[i].empty())
        {
            continue;
        }

        p32 r = {group[i].begin()->x, group[i].rbegin()->x};

        int comp = location(x, r);
        if (comp == 1)
        {
            last = i;
            continue;
        }

        return i;
    }

    if (last != -1)
    {
        return last;
    }

    return 0;
}

void init(int N, int L, int X[])
{
    // ???
    int group_size = sqrt(N);
    fix_size = group_size;
    camera_length = L;

    group.resize(ceil(double(N) / group_size), group_t(camera_length));
    old_group.resize(group.size(), group_t(camera_length));
    position.resize(N);

    for (size_t i = 0; i < N; i++)
    {
        position[i] = X[i];
        group[i / group_size].add(position[i], false);

        // (jei sekantis bus kitoje grupeje)
        if ((i + 1) / group_size > i / group_size)
        {
            group[i / group_size].fix();
        }
    }
}

int call_count = 0;

int update(int i, int y)
{
    if ((call_count + 1) / fix_size > call_count / fix_size)
    {
        fix_everything(group, old_group, fix_size, camera_length);
        swap(group, old_group);
    }

    if (position[i] != y)
    {
        group_t *g = nullptr;

        for (auto &gr : group)
        {
            if (gr.contains(position[i]))
            {
                g = &gr;
            }
        }

        assert(g);
        g->remove(position[i], true);

        int pos = find_insertion(y, group);

        group[pos].add(y, true);
        position[i] = y;
    }

    int count = 0;
    int current = -1;

    for (auto &g : group)
    {
        if (g.empty())
        {
            continue;
        }

        if (g.begin()->camera == 0)
        {
            g.fix();
        }

        auto it = g.first_after(current);
        if (it.x == -1)
        {
            continue;
        }

        count += it.camera;
        current = it.end;
    }

    call_count++;
    return count;
}

Compilation message (stderr)

elephants.cpp:9: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    9 | #pragma region dalykai
      | 
elephants.cpp:56: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   56 | #pragma endregion
      | 
elephants.cpp: In function 'void init(int, int, int*)':
elephants.cpp:279:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  279 |     for (size_t i = 0; i < N; i++)
      |                        ~~^~~

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