oj.uz

Submission #645682

# Submission time Handle Problem Language Result Execution time Memory
645682 2022-09-27T16:07:51 Z pls33 Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 17744 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 : public multiset<elephant_t, comp_t>
{
private:
    int length;

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

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

        auto it = rbegin();

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

        for (; it != rend(); it++)
        {
            auto prev = upper_bound({it->x + length, 0, 0});

            if (prev == 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)
    {
        insert({x, 0, 0});

        if (fix_group)
        {
            fix();
        }
    }

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

        auto it = find({x, 0, 0});
        assert(it != end());

        erase(it);

        if (fix_group)
        {
            fix();
        }
    }

    bool contains(int x)
    {
        return find({x, 0, 0}) != end();
    }

    elephant_t first_after(int x)
    {
        auto it = upper_bound({x, 0, 0});

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

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)
{
    queue<elephant_t> q;

    for (auto &g : g_old)
    {
        for (auto &e : g)
        {
            q.push(e);
        }
        g.clear();
    }

    int i = 0;
    while (!q.empty())
    {
        elephant_t cur = q.front();
        q.pop();

        g_new[i / group_size].add(cur.x, false);

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

        i++;
    }
}

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:248:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  248 |     for (size_t i = 0; i < N; i++)
      |                        ~~^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1314 ms 2732 KB Output is correct
8 Correct 1603 ms 3276 KB Output is correct
9 Correct 2923 ms 5964 KB Output is correct
10 Correct 2376 ms 5708 KB Output is correct
11 Correct 2454 ms 5672 KB Output is correct
12 Correct 3506 ms 5804 KB Output is correct
13 Correct 2437 ms 5552 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1314 ms 2732 KB Output is correct
8 Correct 1603 ms 3276 KB Output is correct
9 Correct 2923 ms 5964 KB Output is correct
10 Correct 2376 ms 5708 KB Output is correct
11 Correct 2454 ms 5672 KB Output is correct
12 Correct 3506 ms 5804 KB Output is correct
13 Correct 2437 ms 5552 KB Output is correct
14 Correct 2100 ms 3924 KB Output is correct
15 Correct 2675 ms 4236 KB Output is correct
16 Correct 4890 ms 6508 KB Output is correct
17 Correct 5923 ms 8164 KB Output is correct
18 Correct 6371 ms 8080 KB Output is correct
19 Correct 5512 ms 8372 KB Output is correct
20 Correct 5873 ms 8276 KB Output is correct
21 Correct 5968 ms 8120 KB Output is correct
22 Correct 3912 ms 7732 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1314 ms 2732 KB Output is correct
8 Correct 1603 ms 3276 KB Output is correct
9 Correct 2923 ms 5964 KB Output is correct
10 Correct 2376 ms 5708 KB Output is correct
11 Correct 2454 ms 5672 KB Output is correct
12 Correct 3506 ms 5804 KB Output is correct
13 Correct 2437 ms 5552 KB Output is correct
14 Correct 2100 ms 3924 KB Output is correct
15 Correct 2675 ms 4236 KB Output is correct
16 Correct 4890 ms 6508 KB Output is correct
17 Correct 5923 ms 8164 KB Output is correct
18 Correct 6371 ms 8080 KB Output is correct
19 Correct 5512 ms 8372 KB Output is correct
20 Correct 5873 ms 8276 KB Output is correct
21 Correct 5968 ms 8120 KB Output is correct
22 Correct 3912 ms 7732 KB Output is correct
23 Execution timed out 9013 ms 17744 KB Time limit exceeded
24 Halted 0 ms 0 KB -