#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(a) a.begin(),a.end()
#define sz(a) (int)(a.size())
#define ub upper_bound
typedef long long int ll;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
typedef pair<int,int> pii;
ll n,l;
VII bucket,reach,cnt;
vector<ll>x,comp;
ll blk = 500,num;
ll find(ll cur,ll val){
ll l = 0,r = sz(bucket[cur])-1;
while(r>=l){
ll mid = (l+r)/2;
if(x[bucket[cur][mid]] <= val)l = mid+1;
else r = mid-1;
}
return l;
}
void build1(vector<ll>a,ll cur){
if(cur == sz(bucket)){
bucket.pb(a);
reach.pb(a);
cnt.pb(a);
}else bucket[cur] = reach[cur] = cnt[cur] = a;
ll last = bucket[cur].back();
for(ll i=sz(a)-1;i>=0;i--){
ll v = bucket[cur][i];
comp[v] = cur;
if(x[v]+l >= x[last]){
reach[cur][i] = x[v]+l;
cnt[cur][i] = 1;
}else{
ll p = find(cur,x[v]+l);
reach[cur][i] = reach[cur][p];
cnt[cur][i] = cnt[cur][p]+1;
}
}
}
void build2(){
bucket.clear();
cnt.clear();
reach.clear();
vector<pii>a;
for(ll i=0;i<n;i++)a.pb({x[i],i});
sort(all(a));
for(ll i=0,j=0;i<n;i+=blk,j++){
vector<ll>b;
for(ll k=i;k<min(n,i+blk);k++)b.pb(a[k].second);
build1(b,j);
}
}
void init(ll N, ll L, ll X[])
{
n = N;
l = L;
x.resize(n);
comp.resize(n);
for(ll i=0;i<n;i++)x[i] = X[i];
build2();
}
ll update(ll i, ll y)
{
if(num == blk-1)build2();
else{
num%=blk;
ll c = comp[i];
vector<ll>a;
for(ll x:bucket[c]){
if(x != i)a.pb(x);
}
build1(a,c);
x[i] = y;
for(ll i=0;i<sz(bucket);i++){
if(y <= x[bucket[i].back()]){
c = i;
break;
}
}
a = bucket[c];
a.pb(i);
sort(all(a),[&](const ll &i,const ll &j){return x[i] < x[j];});
build1(a,c);
}
ll ans = cnt[0][0];
ll cur = reach[0][0];
for(ll i=1;i<sz(bucket);i++){
if(cur >= x[bucket[i].back()])continue;
ll idx = find(i,cur);
cur = reach[i][idx];
ans+=cnt[i][idx];
}
//for(ll i=0;i<n;i++)cout<<x[bucket[0][i]]<<" "<<reach[0][i]<<" "<<cnt[0][i]<<'\n';
num++;
return ans;
}
Compilation message
/usr/bin/ld: /tmp/ccqVk7m4.o: in function `main':
grader.cpp:(.text.startup+0x27): undefined reference to `init(int, int, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x56): undefined reference to `update(int, int)'
collect2: error: ld returned 1 exit status
