oj.uz

Submission #645692

# Submission time Handle Problem Language Result Execution time Memory
645692 2022-09-27T16:34:03 Z pls33 Dancing Elephants (IOI11_elephants) C++17
100 / 100
 7739 ms 17516 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 569 ms 1688 KB Output is correct
8 Correct 670 ms 1844 KB Output is correct
9 Correct 925 ms 2640 KB Output is correct
10 Correct 833 ms 2688 KB Output is correct
11 Correct 869 ms 2688 KB Output is correct
12 Correct 1373 ms 2724 KB Output is correct
13 Correct 788 ms 2688 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 569 ms 1688 KB Output is correct
8 Correct 670 ms 1844 KB Output is correct
9 Correct 925 ms 2640 KB Output is correct
10 Correct 833 ms 2688 KB Output is correct
11 Correct 869 ms 2688 KB Output is correct
12 Correct 1373 ms 2724 KB Output is correct
13 Correct 788 ms 2688 KB Output is correct
14 Correct 837 ms 2516 KB Output is correct
15 Correct 1066 ms 2252 KB Output is correct
16 Correct 1936 ms 2904 KB Output is correct
17 Correct 2261 ms 4916 KB Output is correct
18 Correct 2258 ms 4920 KB Output is correct
19 Correct 1658 ms 4860 KB Output is correct
20 Correct 2197 ms 4912 KB Output is correct
21 Correct 2139 ms 4912 KB Output is correct
22 Correct 1362 ms 4932 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 569 ms 1688 KB Output is correct
8 Correct 670 ms 1844 KB Output is correct
9 Correct 925 ms 2640 KB Output is correct
10 Correct 833 ms 2688 KB Output is correct
11 Correct 869 ms 2688 KB Output is correct
12 Correct 1373 ms 2724 KB Output is correct
13 Correct 788 ms 2688 KB Output is correct
14 Correct 837 ms 2516 KB Output is correct
15 Correct 1066 ms 2252 KB Output is correct
16 Correct 1936 ms 2904 KB Output is correct
17 Correct 2261 ms 4916 KB Output is correct
18 Correct 2258 ms 4920 KB Output is correct
19 Correct 1658 ms 4860 KB Output is correct
20 Correct 2197 ms 4912 KB Output is correct
21 Correct 2139 ms 4912 KB Output is correct
22 Correct 1362 ms 4932 KB Output is correct
23 Correct 6840 ms 7956 KB Output is correct
24 Correct 7405 ms 12992 KB Output is correct
25 Correct 5457 ms 12984 KB Output is correct
26 Correct 6218 ms 12988 KB Output is correct
27 Correct 7203 ms 12748 KB Output is correct
28 Correct 944 ms 5324 KB Output is correct
29 Correct 937 ms 5264 KB Output is correct
30 Correct 948 ms 5264 KB Output is correct
31 Correct 998 ms 5196 KB Output is correct
32 Correct 5659 ms 12368 KB Output is correct
33 Correct 6653 ms 11692 KB Output is correct
34 Correct 5092 ms 12640 KB Output is correct
35 Correct 7021 ms 17516 KB Output is correct
36 Correct 5838 ms 12404 KB Output is correct
37 Correct 7527 ms 16040 KB Output is correct
38 Correct 5253 ms 11552 KB Output is correct
39 Correct 5984 ms 12692 KB Output is correct
40 Correct 5035 ms 11636 KB Output is correct
41 Correct 7739 ms 12428 KB Output is correct
42 Correct 7528 ms 12644 KB Output is correct