/**
* author: wxhtzdy
* created: 20.07.2022 11:59:55
**/
#include "elehpants.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 150005;
const int BLOCK = sqrt(N);
int n, l, x[N], cnt[N], pos[N];
int id[N], order[N];
vector<int> idx[N / BLOCK];
void BuildBlock(int i) {
sort(idx[i].begin(), idx[i].end(), [&](int a, int b) {
if (x[a] != x[b]) {
return x[a] < x[b];
} else {
return a < b;
}
});
int sz = (int) idx[i].size();
int ptr = sz - 1;
for (int j = sz - 1; j >= 0; j--) {
if (x[idx[i][sz - 1]] - x[idx[i][j]] <= l) {
cnt[idx[i][j]] = 1;
pos[idx[i][j]] = x[idx[i][j]] + l;
} else {
while (x[idx[i][ptr]] - x[idx[i][j]] > l) {
ptr -= 1;
}
cnt[idx[i][j]] = cnt[idx[i][ptr + 1]] + 1;
pos[idx[i][j]] = pos[idx[i][ptr + 1]];
}
}
}
void Build() {
for (int i = 0; i < n; i++) {
order[i] = i;
}
sort(order, order + n, [&](int i, int j) {
if (x[i] != x[j]) {
return x[i] < x[j];
} else {
return i < j;
}
});
for (int i = 0; i <= n / BLOCK; i++) {
idx[i].clear();
}
for (int i = 0; i < n; i++) {
id[order[i]] = i / BLOCK;
idx[id[order[i]]].push_back(order[i]);
}
for (int i = 0; i <= n / BLOCK; i++) {
BuildBlock(i);
}
}
int Q;
int update(int i, int y) {
++Q;
x[i] = y;
if (Q == BLOCK / 5) {
Build();
Q = 0;
} else {
vector<int> b;
bool found = false;
for (int j = 0; j < (int) idx[id[i]].size(); j++) {
if (idx[id[i]][j] != i) {
b.push_back(idx[id[i]][j]);
} else {
found = true;
}
}
assert(found);
idx[id[i]] = b;
BuildBlock(id[i]);
b.clear();
for (int j = n / BLOCK; j >= 0; j--) {
if (!idx[j].empty() && x[idx[j][0]] <= y) {
id[i] = j;
break;
}
}
idx[id[i]].push_back(i);
/*if (idx[id[i]].empty() || x[idx[id[i]].back()] < y) {
} else {
vector<int> b;
for (int j = 0; j < (int) idx[id[i]].size(); j++) {
if (y <= x[idx[id[i]][j]]) {
b.push_back(i);
y = (int) 1.01e9;
j -= 1;
} else {
b.push_back(idx[id[i]][j]);
}
}
idx[id[i]] = b;
}*/
BuildBlock(id[i]);
}
//Build(); // brute force check
int ans = 0, R = -1;
for (int i = 0; i <= n / BLOCK; i++) {
if (idx[i].empty() || x[idx[i].back()] <= R) {
continue;
}
int low = 0, high = (int) idx[i].size() - 1, at = 0;
while (low <= high) {
int mid = low + high >> 1;
if (x[idx[i][mid]] > R) {
at = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
assert(R < x[idx[i][at]] && (at == 0 || R >= x[idx[i][at - 1]]));
ans += cnt[idx[i][at]];
R = pos[idx[i][at]];
}
return ans;
}
void init(int n, int l, int x[]) {
::n = n;
::l = l;
for (int i = 0; i < n; i++) {
::x[i] = x[i];
}
Build();
}
Compilation message
elephants.cpp:5:10: fatal error: elehpants.h: No such file or directory
5 | #include "elehpants.h"
| ^~~~~~~~~~~~~
compilation terminated.
