// Jun 21 2015, minsu( github : https://github.com/minsuu/ )
#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
const int MAXN = 150015;
const int BLOCK = 400;
int n,bn, K, beg[BLOCK], ele[MAXN], tmp[MAXN], cooltime;
vector<int> pos[BLOCK], ans[BLOCK], lim[BLOCK];
void construct( int b ){
for(int i = (int)pos[b].size(); i>=0; i--){
int p = lower_bound( pos[b].begin(), pos[b].end(), pos[b][i] + K + 1 ) - pos[b].begin();
if( p == pos[b].size() )
ans[b][i] = 1, lim[b][i] = pos[b][i] + K + 1;
else
ans[b][i] = ans[b][p] + 1, lim[b][i] = lim[b][p];
}
}
void init(int N, int L, int X[])
{
n = N; K = L;
for(int i=0; i<n; i++){
int b = i / BLOCK; ele[i] = X[i];
pos[b].push_back( X[i] );
ans[b].push_back( 0 );
lim[b].push_back( 0 );
} bn = (n-1) / BLOCK + 1;
for(int i=0;i<bn;i++){
construct(i);
beg[i] = pos[i].back();
}
}
int update(int i, int y)
{
if( cooltime == BLOCK ){
ele[i] = y;
memcpy( tmp, ele, n * sizeof(int)); sort( temp, tmp+n );
for(int i=0; i<bn; i++) pos[i].clear(), ans[i].clear(), lim[i].clear();
init( n, K, tmp );
cooltime = 0;
}else{
int x = ele[i]; ele[i] = y; cooltime++;
int xb = lower_bound( beg, beg+bn, x ) - beg;
int xp = lower_bound( pos[xb].begin(), pos[xb].end(), x) - pos[xb].begin();
pos[xb].erase( pos[xb].begin() + xp ); ans[xb].pop_back(); lim[xb].pop_back();
construct(xb);
if( pos[xb].size() != 0) beg[xb] = pos[xb].back();
int yb = lower_bound( beg, beg+bn, y ) - beg; if( yb == bn ) yb--;
int yp = lower_bound( pos[yb].begin(), pos[yb].end(), y) - pos[yb].begin();
pos[yb].insert( pos[yb].begin() + yp, y ); ans[yb].push_back(0); lim[yb].push_back(0);
construct(yb); beg[yb] = pos[yb].back();
}
int np = 0, ret = 0;
for(int i=0; i<bn; i++){
int sp = lower_bound( pos[i].begin(), pos[i].end(), np ) - pos[i].begin();
ret += ans[i][sp]; np = lim[i][sp];
}
return ret;
}
Compilation message
elephants.cpp: In function ‘void construct(int)’:
elephants.cpp:14:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if( p == pos[b].size() )
^
elephants.cpp: In function ‘int update(int, int)’:
elephants.cpp:40:45: error: ‘temp’ was not declared in this scope
memcpy( tmp, ele, n * sizeof(int)); sort( temp, tmp+n );
^
