#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 = min(N, int(sqrt(N) * log2(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++)
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 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 |
8274 ms |
1816 KB |
Output is correct |
| 8 |
Execution timed out |
9007 ms |
2132 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 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 |
8274 ms |
1816 KB |
Output is correct |
| 8 |
Execution timed out |
9007 ms |
2132 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 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 |
8274 ms |
1816 KB |
Output is correct |
| 8 |
Execution timed out |
9007 ms |
2132 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
