#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
const int k = 400;
int n, l, cnt = 0;
vector<int> positions;
vector<vector<int>> buckets;
vector<int> bucketStarts, bucketEnds;
vector<vector<pair<int, int>>> bucketDps;
void doDp(int bucket) {
// cout << "Do DP: " << bucket << endl;
vector<int> &curBucket = buckets[bucket];
vector<pair<int, int>> &curDp = bucketDps[bucket];
int sz = curBucket.size();
if (!sz) {
bucketStarts[bucket] = (bucket ? bucketStarts[bucket - 1] : -1);
bucketEnds[bucket] = (bucket ? bucketEnds[bucket - 1] : -1);
return;
}
curDp.assign(sz, {0, 0});
curDp[sz - 1] = {1, curBucket[sz - 1] + l};
int j = sz - 1;
for (int i = sz - 2; i >= 0; --i) {
while (curBucket[j] > curBucket[i] + l) --j;
if (j < sz - 1) curDp[i] = {1 + curDp[j + 1].first, curDp[j + 1].second};
else curDp[i] = {1, curBucket[i] + l};
}
bucketStarts[bucket] = curBucket[0];
bucketEnds[bucket] = curBucket[sz - 1];
}
void build() {
buckets.clear();
bucketStarts.clear();
bucketEnds.clear();
bucketDps.clear();
vector<int> elephants(n);
for (int i = 0; i < n; ++i) elephants[i] = positions[i];
sort(elephants.begin(), elephants.end());
buckets.resize((n - 1) / k + 1);
for (int i = 0; i < n; ++i) buckets[i / k].push_back(elephants[i]);
for (int i = 0; i < buckets.size(); ++i) bucketDps.push_back({}), bucketStarts.push_back(-1), bucketEnds.push_back(-1), doDp(i);
}
void print()
{
cout << n << ' ' << l << ' ' << cnt << endl;
cout << "Positions: " << endl;
for (int &i : positions) cout << i << ' ';
cout << endl;
cout << "Buckets: " << endl;
for (auto &i : buckets) {
for (int &j : i) cout << j << ' ';
cout << endl;
}
cout << "Bucket Starts: " << endl;
for (int &i : bucketStarts) cout << i << ' ';
cout << endl;
cout << "Bucket Ends: " << endl;
for (int &i : bucketEnds) cout << i << ' ';
cout << endl;
cout << "Bucket DP: " << endl;
for (auto &i : bucketDps) {
for (auto &j : i) cout << j.first << ' ' << j.second << " ";
cout << endl;
}
}
int solve() {
// print();
int curRes = 0, curEnd = 0;
int bucketCount = buckets.size();
for (int i = 0; i < bucketCount; ++i) {
if (!buckets[i].empty()) {
curRes = bucketDps[i][0].first, curEnd = bucketDps[i][0].second;
break;
}
}
// cout << "SOLVE: " << endl;
// cout << curRes << ' ' << curEnd << endl;
int j = 0;
while (j < bucketCount - 1) {
++j;
// cout << "J(0): " << j << endl;
if (curEnd >= bucketEnds[j]) continue;
// cout << "J(1): " << j << endl;
int pos = upper_bound(buckets[j].begin(), buckets[j].end(), curEnd) - buckets[j].begin();
// cout << "POS: " << pos << endl;
curRes += bucketDps[j][pos].first;
curEnd = bucketDps[j][pos].second;
// cout << curRes << ' ' << curEnd << endl;
}
return curRes;
}
void init(int N, int L, int X[])
{
n = N;
l = L;
for (int i = 0; i < N; ++i) positions.push_back(X[i]);
}
int update(int i, int y)
{
if (cnt % k == 0) build();
int bucketCount = buckets.size();
int a = 0, b = 0;
while (a < bucketCount) {
if (bucketEnds[a] >= positions[i]) break;
++a;
}
while (b < bucketCount) {
if (bucketEnds[b] >= y) break;
++b;
}
b = min(b, bucketCount - 1);
buckets[a].erase(lower_bound(buckets[a].begin(), buckets[a].end(), positions[i]));
positions[i] = y;
buckets[b].push_back(positions[i]);
sort(buckets[b].begin(), buckets[b].end());
doDp(a);
if (a != b) doDp(b);
++cnt;
return solve();
}
