#include "elephants.h"
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;
const int MAX = 1e3 + 15;
int n, L, x[MAX], block[MAX], T, dist[MAX], dp[MAX], q;
vector<int> ord, blocks[MAX];
bool cmp(int i, int j){ return x[i] < x[j]; }
void init(int n_, int l_, int x_[]){
n = n_, L = l_;
T = sqrt(n) + 1;
for(int i = 0; i < n; i++)
x[i] = x_[i];
for(int i = 0; i < n; i++)
ord.push_back(i);
}
void buildBlock(int b){
int s = sz(blocks[b]), lst = x[blocks[b].back()];
for(int l = s - 1, r = s - 1; l >= 0; l--){
int curId = blocks[b][l], curPos = x[curId];
if(lst - curPos <= l){
dp[curId] = 1;
dist[curId] = curPos + L;
}else{
while(x[blocks[b][r]] - curPos > l) r--;
dp[curId] = dp[blocks[b][r]] + 1;
dist[curId] = dist[blocks[b][r]];
}
}
}
void build(){
for(int i = 0; i <= (n - 1) / T; i++)
blocks[i].clear();
sort(all(ord), cmp);
for(int i = 0; i < n; i++){
block[ord[i]] = i / T;
blocks[i / T].push_back(ord[i]);
}
for(int i = 0; i <= (n - 1) / T; i++)
buildBlock(i);
}
int query(){
int resp = 0;
for(int i = 0, t = -1; i <= (n - 1) / T; i++){
if(blocks[i].empty() || t >= x[blocks[i].back()]) continue;
int l = 0, r = sz(blocks[i]) - 1, jump = 0;
while(l <= r){
int m = (l + r) >> 1;
int curPos = x[blocks[i]][m]];
if(curPos > t) jump = m, l = m + 1;
else r = m - 1;
}
resp += dp[blocks[i][jump]];
t = dist[blocks[i][jump]];
}
return resp;
}
int update(int i, int y){
if(q % T == 0) build();
q++;
//Remove from current block
vector<int> aux;
for(auto x : blocks[i]){
if(x == i) continue;
aux.push_back(x);
}
swap(aux, blocks[block[i]]);
buildBlock(block[i]);
//Add to new block
aux.clear();
int newBlock = 0;
for(int j = 0; j <= (n - 1) / T; j++)
if(blocks[j].size() && blocks[j].back() >= y){ newBlock = j; break; }
aux.push_back(i);
x[i] = y;
vector<int> ret(sz(blocks[newBlock]) + 1);
merge(aux.begin(), aux.end(), blocks[newBlock].begin(), blocks[newBlock].end(), ret.begin(), cmp);
swap(ret, blocks[newBlock]);
buildBlock(newBlock);
return query();
}
Compilation message
elephants.cpp: In function 'int query()':
elephants.cpp:71:21: error: no match for 'operator[]' (operand types are 'int [1015]' and 'std::vector<int>')
71 | int curPos = x[blocks[i]][m]];
| ^
