//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "elephants.h"
//#include "grader.h"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long int ll;
const int INF = 1e9 + 7;
const int MAXN = 15e4 + 5;
const int BLOCK = 513;
int n, l, a[MAXN], b[MAXN], st[MAXN];
int bcnt = 1, buc[BLOCK][2 * BLOCK + 1];
int val[BLOCK][2 * BLOCK + 1][2];
map<int,int> cnt;
void calc(int ind) {
int sz = buc[ind][0];
for (int i = sz; i > 0; i--) {
while (sz > 0 && buc[ind][i] + l < buc[ind][sz])
sz--;
if (sz < buc[ind][0]) {
val[ind][i][0] = val[ind][sz + 1][0] + 1;
val[ind][i][1] = val[ind][sz + 1][1];
} else {
val[ind][i][0] = 1;
val[ind][i][1] = buc[ind][i];
}
}
}
void build() {
bcnt = 1;
for (int i = 0; i * BLOCK < n; i++) {
bcnt++;
buc[i][0] = 0;
for (int j = 0; j < BLOCK && BLOCK * i + j < n; j++)
buc[i][++buc[i][0]] = b[BLOCK * i + j];
calc(i);
st[i] = buc[i][1];
}
}
void init(int N, int L, int X[]) {
n = N, l = L;
for (int i = 0; i < n; i++) {
a[i] = X[i], b[i] = X[i];
cnt[X[i]]++;
}
n = cnt.size();
build();
}
void restore() {
int cur = 0;
for (int i = 0; i < bcnt; i++)
for (int j = 1; j <= buc[i][0])
b[cur++] = buc[i][j];
}
int getBucket(int pos) {
return lower_bound(st + 1, st + bcnt, pos + 1) - st - 1;
}
int update(int ind, int pos) {
cnt[a[ind]]--;
if (cnt[a[ind]] == 0) {
int b = getBucket(a[ind]);
int st = lower_bound(buc[b] + 1, buc[b] + buc[b][0] + 1, a[ind]) - buc[b];
for (int i = st; i <= buc[b][0]; i++)
buc[b][i] = buc[b][i + 1];
n--, buc[b][0]--;
calc(b);
}
cnt[pos]++;
if (cnt[pos] == 1) {
int b = getBucket(pos);
if (buc[b][0] == 2 * BLOCK) {
restore();
build();
b = getBucket(pos);
}
int st = lower_bound(buc[b] + 1, buc[b] + buc[b][0] + 1, pos) - buc[b];
for (int i = buc[b][0] + 1; i > st; i--)
buc[b][i] = buc[b][i - 1];
buc[b][st] = pos;
n++, buc[b][0]++;
calc(b);
}
a[ind] = pos;
int ret = 0, cur = -INF;
for (int i = 0; i < bcnt; i++) {
int nx = lower_bound(buc[i] + 1, buc[i] + buc[i][0] + 1, cur + l + 1) - buc[i];
if (nx > buc[i][0]) continue; // picture ends in the next bucket
ret += val[i][nx][0];
cur = val[i][nx][1];
}
return ret;
}
Compilation message
elephants.cpp: In function 'void restore()':
elephants.cpp:63:33: error: expected ';' before ')' token
for (int j = 1; j <= buc[i][0])
^
