#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
constexpr int maxn = 70000 + 10;
map<int, int> m;
int n, l, r, b; // r blocks of size b
struct Node {
int siz;
// Positions of the elephants sorted. First is first element, last is last element
// Number of cameras starting in this group given that a number of elephants in allready
// acounted for
vector <pii> cam;
// cam[i] means number of cameras needed given that i-th elephant is first we need
vector <int> pos;
void init(const vector <int> &positions)
{
pos = positions;
siz = positions.size();
calc();
}
void ins(const int &p, vector <Node>&grou) // O(r + r ** 2)
{
pos.insert(upper_bound(pos.begin(), pos.end(), p), p);
siz++;
if (!split(grou)) calc();
}
void rem(const int &p) // O(r + r**2)
{
pos.erase(lower_bound(pos.begin(), pos.end(), p));
siz--;
calc();
}
void calc() // O(r**2 )
{
cam = vector <pii> (siz + 1);
cam[siz].first = 0; // All elephants are covered
cam[siz].second = -1;
int furthest;
for (int y = 0; y < siz; y++)
{
furthest = -1;
for (int i = y; i < siz; i++)
{
if (pos[i] > furthest)
{
furthest = pos[i] + l;
cam[y].first++;
}
}
cam[y].second = furthest;
}
}
int find_group(int pos, vector <Node>&grou) // O(log(r))
{
int lower = 0, higher = grou.size() - 1, mid;
while (lower != higher)
{
mid = (lower + higher + 1) >> 1;
if (grou[mid].pos.size() == 0 || grou[mid].pos[0] > pos) higher = mid - 1;
else lower = mid;
}
return lower;
}
// Function for splitting the group if it is 2r in size
bool split(vector <Node>&grou) //O(r + r**2)
{
if (siz < (b * 3) / 2) return false;
Node new_group;
int mid = siz / 2;
new_group.init(vector<int>(pos.begin() + mid, pos.end()));
grou.insert(grou.begin() + find_group(pos[0], grou) + 1, new_group);
pos.resize(mid);
siz = mid;
calc();
return true;
}
} ;
vector <Node> groups(r);
void print_groups()
{
cout << r << "\n";
for (int i = 0; i < r; i++)
{
cout << i << "\n";
cout << groups[i].siz << "\n";
if (groups[i].siz == 0) continue;
for (int q : groups[i].pos) cout << q << " ";
cout << "\n";
for (pii q : groups[i].cam) cout << q.first << " ";
cout << "\n";
for (pii q : groups[i].cam) cout << q.second << " ";
cout << "\n\n";
}
}
int all() // O(n log(n / r) / r)
{
int out = 0,
furthest = -1,
pos;
for (auto g : groups) {
if (g.siz == 0) continue;
pos = upper_bound(g.pos.begin(), g.pos.end(), furthest) - g.pos.begin();
out += g.cam[pos].first;
furthest = max(furthest, g.cam[pos].second);
}
return out;
}
void init(int N, int L, int X[])
{
n = N, l = L;
r = sqrt(n), b = 1 + n / r; // r blocks of size b
// Keeping track of the positions of the elephants by number
for (int i = 0; i < n; i++) // O(n log(n))
{
m.insert(pii(i, X[i]));
}
int i;
for (i = 0; i < n - b; i += b) // O(n + (n*r**2)/r)
{
groups[i / b].init(vector<int>(X + i, X + i + b));
}
groups[i / b].init(vector<int>(X + i, X + n));
}
int update(int i, int y)
{
groups[groups[0].find_group(m[i], groups)].rem(m[i]); // O(log(n/r) + r**2)
m[i] = y;
groups[groups[0].find_group(y, groups)].ins(y, groups); // O(log(n/r) + r**2)
return all();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
