#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define F first
#define S second
#define debug(x) cerr<<#x<<" :"<<x<<"\n"
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define FAST ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
#define int long long
typedef long long ll;
typedef long double ld;
const int maxn = 1.5e5 + 7;
const int mod = 1e9 + 7;
const int INF = 2e9 + 7;
const int mlog = 20;
const int SQRT = 400;
int n, k;
int bcnt;
int R[SQRT + 7];
int pos[maxn];
map<int, int> mp;
vector<int> jump[SQRT + 7], cnt[SQRT + 7], bucket[SQRT + 7];
void solve(int ind)
{
jump[ind] = vector<int>(bucket[ind].size());
cnt[ind] = vector<int>(bucket[ind].size());
for(int i = bucket[ind].size() - 1, j = bucket[ind].size(); ~i; i--)
{
while(bucket[ind][j - 1] > bucket[ind][i] + k)
j--;
if(j < bucket[ind].size()) jump[ind][i] = jump[ind][j], cnt[ind][i] = cnt[ind][j] + 1;
else jump[ind][i] = bucket[ind][i] + k, cnt[ind][i] = 1;
}
}
void add(int x, bool rmv)
{
int ptr = -1;
while(R[++ptr] < x);
int ind = lower_bound(bucket[ptr].begin(), bucket[ptr].end(), x) - bucket[ptr].begin();
if(rmv) bucket[ptr].erase(bucket[ptr].begin() + ind);
else bucket[ptr].insert(bucket[ptr].begin() + ind, x);
solve(ptr);
}
void REBUILD()
{
bcnt = 0;
for(pii p : mp)
{
if(!bcnt || bucket[bcnt - 1].size() >= SQRT)
bucket[bcnt++].clear();
bucket[bcnt - 1].pb(p.F);
}
for(int i = 0; i < bcnt; i++)
{
if(i < bcnt - 1) R[i] = bucket[i + 1][0] - 1;
else R[i] = +INF;
solve(i);
}
}
void init(int _n, int _k, int X[])
{
n = _n, k = _k;
for(int i = 0; i < n; i++) ++mp[pos[i] = X[i]];
}
int cntBLOCK;
int update(int i,int y)
{
if(cntBLOCK++ % SQRT == 0)
REBUILD();
if(!--mp[pos[i]]) add(pos[i], 0), mp.erase(pos[i]);
if(!mp[y]) add(y, 1);
mp[y]++, pos[i] = y;
int ans = 0, cur = -1;
for(int i = 0; i < bcnt; i++)
{
int ind = upper_bound(bucket[i].begin(), bucket[i].end(), cur) - bucket[i].begin();
if(ind < bucket[i].size())
ans += cnt[i][ind], cur = jump[i][ind];
}
return ans;
}
Compilation message
elephants.cpp: In function 'void solve(long long int)':
elephants.cpp:43:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | if(j < bucket[ind].size()) jump[ind][i] = jump[ind][j], cnt[ind][i] = cnt[ind][j] + 1;
| ~~^~~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'long long int update(long long int, long long int)':
elephants.cpp:101:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | if(ind < bucket[i].size())
| ~~~~^~~~~~~~~~~~~~~~~~
/tmp/ccXtvaun.o: In function `main':
grader.cpp:(.text.startup+0x23): undefined reference to `init(int, int, int*)'
grader.cpp:(.text.startup+0x55): undefined reference to `update(int, int)'
collect2: error: ld returned 1 exit status
