#include "elephants.h" #include <vector> #include <iostream> #include <algorithm> using namespace std; const long long maxN = 150'000; // const long long rt = 1000; //change value and check const long long block_count = 500; const long long block_size = 500; const long long recompute_freq = 100; //block_size * block_count >= maxN using vi = vector<long long>; long long N; long long L; long long* X; long long* I; void init(int N_, int L_, int X_[]) { N = N_; L = L_; X = new long long[N]; for(long long i = 0; i < N; i++) X[i] = X_[i]; I = new long long[N]; for(long long i = 0; i < N; i++) I[i] = i; // cerr << "check\n"; // cerr << "L = " << L << '\n'; } long long sz[block_count]; long long blocklist[block_count][block_size + recompute_freq]; long long block[5 + maxN]; long long camera_count[5 + maxN]; long long camera_reach[5 + maxN]; void compute_block(long long b) { sort(blocklist[b], blocklist[b] + sz[b], [] (long long u, long long v) { return X[u] < X[v]; }); long long r = sz[b] - 1; for(long long l = sz[b] - 1; l >= 0; l--) { while(X[blocklist[b][r]] - X[blocklist[b][l]] > L) r--; if(r == sz[b] - 1) { camera_count[blocklist[b][l]] = 1; camera_reach[blocklist[b][l]] = X[blocklist[b][l]] + L; } else { camera_count[blocklist[b][l]] = 1 + camera_count[blocklist[b][r+1]]; camera_reach[blocklist[b][l]] = camera_reach[blocklist[b][r+1]]; } } } void rebuild() { sort(I, I+N, [] (long long p, long long q) { return X[p] < X[q]; }); for(long long q = 0; q < block_count; q++) sz[q] = 0; for(long long x = 0; x < N; x++) { long long i = I[x]; block[i] = x/block_size; blocklist[x/block_size][x%block_size] = i; sz[x/block_size]++; } for(long long b = 0; b < block_count; b++) compute_block(b); } void erase_elephant(long long oldblock, long long i) { for(long long f = 0; f+1 < sz[oldblock]; f++) { if(blocklist[oldblock][f] == i) swap(blocklist[oldblock][f], blocklist[oldblock][f+1]); } sz[oldblock]--; compute_block(oldblock); } void insert_elephant(long long newblock, long long i) { block[i] = newblock; sz[newblock]++; blocklist[newblock][sz[newblock]-1] = i; compute_block(newblock); } void change_X(long long i, long long y) { long long oldblock = block[i]; long long newblock = -1; long long newblock_score = 2'000'000'001; for(long long b = 0; b < block_count; b++) { if(!sz[b]) continue; long long curr_score = abs(X[blocklist[b][0]] - y) + abs(X[blocklist[b][sz[b] - 1]] - y); if(curr_score < newblock_score) { newblock = b; newblock_score = curr_score; } } long long oldX = X[i]; X[i] = y; erase_elephant(oldblock, i); insert_elephant(newblock, i); } long long answer() { long long res = 0; long long b = 0; while(sz[b] == 0) b++; long long st = blocklist[b][0]; while(1) { // cerr << "st = " << st << '\n'; long long rc = camera_reach[st]; res += camera_count[st]; bool nonext = 0; while(1) { if(b >= block_count) { nonext = 1; break; } if(sz[b] == 0) { b++; continue; } if(X[blocklist[b][sz[b] - 1]] <= rc) { b++; continue; } break; } // cerr << "b = " << b << '\n'; // cerr << X[blocklist[b][sz[b] - 1]] << '\n'; if(nonext) return res; long long lo = 0; long long hi = sz[b] - 1; while(lo != hi) { long long mid = (lo+hi)/2; if(X[blocklist[b][mid]] <= rc) lo = mid+1; else hi = mid; } st = blocklist[b][lo]; } return -1; } long long u_ct = -1; int update(int i, int y) { // cerr << "starting update\n"; u_ct++; if(u_ct % recompute_freq == 0) { X[i] = y; rebuild(); } else { change_X(i, y); } // cerr << "ending update\n"; return answer(); }

elephants.cpp: In function 'void change_X(long long int, long long int)':
elephants.cpp:137:15: warning: unused variable 'oldX' [-Wunused-variable]
  137 |     long long oldX = X[i];
      |               ^~~~