#include "elephants.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
int L;
struct Part {
vector<int> Ps;
vector<pii> ans;
void calc_ans() {
ans.resize(Ps.size());
if (ans.empty())
return;
ans.back() = {1, Ps.back() + L};
size_t ptr = ans.size();
LoopR (i,0,(ll)ans.size()-1) {
while (Ps[ptr-1] - Ps[i] > L)
--ptr;
ans[i].first = ptr == ans.size()? 1: ans[ptr].first + 1;
ans[i].second = ptr == ans.size()? Ps[i] + L: ans[ptr].second;
}
}
// vec must be sorted
// O(vec.size())
Part(const vector<int> &vec) {
Ps = vec;
calc_ans();
}
auto lower_bound(int x) {
// implement caching mechanism if needed
return std::lower_bound(Ps.begin(), Ps.end(), x);
}
// O(log(Ps.size()))
pii get(int p) {
auto it = lower_bound(p);
if (it == Ps.end())
return {0, p};
return ans[it - Ps.begin()];
}
// O(Ps.size())
void put(int x) {
auto it = lower_bound(x);
Ps.insert(it, x);
calc_ans();
}
// O(Ps.size())
void remove(int x) {
auto it = lower_bound(x);
assert(it != Ps.end() && *it == x);
Ps.erase(it);
calc_ans();
}
};
struct PartList {
vector<Part> parts;
vector<int> bounds;
map<int, int> pos_cnt;
static constexpr int S = 1280;
// O(nlog(n))
void init(vector<int> vec) {
pos_cnt.clear();
sort(vec.begin(), vec.end());
for (int x : vec)
pos_cnt[x]++;
repart(vec);
}
// Ps must be sorted
// O(Ps.size())
void repart(const vector<int> &Ps) {
bounds.clear();
parts.clear();
for (size_t i = 0; i < Ps.size(); i += S) {
size_t j = min(i + S, Ps.size());
if (j != Ps.size())
bounds.push_back(Ps[j]);
parts.emplace_back(vector(Ps.begin() + i, Ps.begin() + j));
}
}
// O(n)
void repart() {
vector<int> vec;
for (auto &p : parts)
vec.insert(vec.end(), p.Ps.begin(), p.Ps.end());
repart(vec);
}
// O(log(n) + S) + amortized O(n/S)
void move(int x, int y) {
auto &cntx = pos_cnt[x];
auto &cnty = pos_cnt[y];
if (!--cntx) {
int i = upper_bound(bounds.begin(), bounds.end(), x) - bounds.begin();
parts[i].remove(x);
}
if (!cnty++) {
int i = upper_bound(bounds.begin(), bounds.end(), y) - bounds.begin();
parts[i].put(y);
if (parts[i].Ps.size() > 2*S)
repart();
}
}
// O(n/S * log(S))
int calc() {
int ans = 0;
int pnt = 0;
for (auto &p : parts) {
auto [x, y] = p.get(pnt);
//cerr << "Ps = ";
//for (auto x : p.Ps)
// cerr << x << ", ";
//cerr << "\npnt = " << pnt << ", x = " << x << ", y = " << y << '\n';
ans += x;
pnt = y;
}
return ans;
}
};
const int N = 150'010;
PartList part_list;
int pos[N];
int n;
void init(int n_, int L_, int X[])
{
n = n_;
L = L_ + 1;
Loop (i,0,n)
pos[i] = X[i];
part_list.init(vector(pos, pos + n));
}
int update(int i, int y)
{
part_list.move(pos[i], y);
pos[i] = y;
return part_list.calc();
}
// move = O(log(n) + S) + amortized O(n/S)
// calc = O(n/S * log(S))
// q log(n) + qS + nq/S + nq/S log(S)
// qS + nq/S log(S)
// S^2 / log(S) = n
// S = 1280
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
452 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
452 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
452 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
452 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
452 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
