#include "elephants.h"
#include "bits/stdc++.h"
using namespace std;
const int B = 370;
int n, l;
int tot, qc;
vector<int> a;
vector<int> bucket;
vector<int> nxt, cnt;
vector<int> in_bucket[B];
inline void calc(int bucket_num) {
int m = in_bucket[bucket_num].size();
if (m == 0) {
return;
}
int p = m - 1;
for (int i = m - 1; i >= 0; --i) {
int cur = in_bucket[bucket_num][i];
while (a[in_bucket[bucket_num][p]] - a[cur] > l) {
p--;
}
if (p == m - 1) {
cnt[cur] = 1;
nxt[cur] = a[cur] + l;
} else {
nxt[cur] = nxt[in_bucket[bucket_num][p + 1]];
cnt[cur] = cnt[in_bucket[bucket_num][p + 1]] + 1;
}
}
}
inline void init(int N_, int L, int X[]) {
n = N_, l = L;
a.resize(n);
cnt.resize(n);
nxt.resize(n);
bucket.resize(n);
tot = (n - 1) / B;
for (int i = 0; i < n; ++i) {
a[i] = X[i];
}
for (int i = 0; i < n; ++i) {
in_bucket[i / B].push_back(i);
bucket[i] = i / B;
}
for (int i = 0; i <= tot; ++i) {
calc(i);
}
}
inline int search(int x) {
for (int i = 0; i <= tot; ++i) {
if (!in_bucket[i].empty() && a[in_bucket[i].back()] > x) {
for (int j : in_bucket[i]) {
if (a[j] > x) {
return j;
}
}
assert(false);
}
}
return -1;
}
inline int query() {
int ret = 0;
int x = -1;
while (true) {
int nb = search(x);
if (nb == -1) {
break;
}
x = nxt[nb];
ret += cnt[nb];
}
return ret;
}
inline void rebuild() {
qc = 0;
vector<int> p;
for (int i = 0; i <= tot; ++i) {
for (int j : in_bucket[i]) {
p.push_back(j);
}
in_bucket[i].clear();
}
for (int i = 0; i < n; ++i) {
in_bucket[i / B].push_back(p[i]);
bucket[p[i]] = i / B;
}
for (int i = 0; i <= tot; ++i) {
calc(i);
}
}
int update(int i, int y) {
qc++;
if (qc == B) {
rebuild();
}
int b1 = bucket[i];
in_bucket[b1].erase(find(in_bucket[b1].begin(), in_bucket[b1].end(), i));
int b2 = search(y);
if (b2 == -1) {
b2 = tot;
} else {
b2 = bucket[b2];
}
bucket[i] = b2;
bool f = false;
for (int j = 0; j < (int) in_bucket[b2].size(); ++j) {
if (a[in_bucket[b2][j]] > y) {
f = true;
in_bucket[b2].insert(in_bucket[b2].begin() + j, i);
break;
}
}
if (!f) {
in_bucket[b2].push_back(i);
}
a[i] = y;
calc(b1);
calc(b2);
return query();
}
Compilation message
/usr/bin/ld: /tmp/ccP9GkGH.o: in function `main':
grader.cpp:(.text.startup+0x27): undefined reference to `init(int, int, int*)'
collect2: error: ld returned 1 exit status
