#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 2e5 + 5;
const int b = 400;
int n, l, m, X[NMAX], q, cnt[NMAX], d[NMAX];
vector<pair<int, int>> v[b];
void init(int n_, int l_, int X_[]){
n = n_; l = l_;
for(int i = 0; i < n; i++) {
X[i] = X_[i];
v[0].emplace_back(X[i], i);
}
sort(all(v[0]));
return;
}
void go(int k){
if(v[k].empty()) return;
int sz = v[k].size();
int ii = sz;
for(int i = sz - 1; i >= 0; i--){
auto&[x, ix] = v[k][i];
while(v[k][ii - 1].first - x > l) ii--;
if(ii == sz){
cnt[ix] = 1;
d[ix] = x + l;
}
else {
int p = v[k][ii].second;
cnt[ix] = cnt[p] + 1;
d[ix] = d[p];
}
}
return;
}
void build(){
vector<pair<int, int>> t;
for(int i = 0; i < b; i++){
for(auto& p : v[i]) t.emplace_back(p);
v[i].clear();
}
for(int i = 0; i < n; i++) v[i / b].emplace_back(t[i]);
for(int i = 0; i < b; i++) go(i);
return;
}
int find(int x){
int ret = 0;
for(int i = 0; i < b; i++)
if(v[i].size() && (v[i][0].first > X[x] || v[i][0].first == X[x] && v[i][0].second <= X[x]) ret = i;
return ret;
}
int update(int i, int y){
if(q++ % b == 0) build();
int k = find(i);
v[k].erase(lower_bound(all(v[k]), make_pair(X[i], i)));
go(k);
X[i] = y;
k = find(i);
auto it = lower_bound(all(v[k]), make_pair(X[i], i));
if(it == v[k].end()) v[k].emplace_back(X[i], i);
else v[k].insert(it, {X[i], i});
go(k);
//cout << "turns is " << q << '\n';
//for(auto&[x, ix] : v[0]) cout << x << ' ';
//cout << '\n';
int ans = 0, e = -2;
for(int i = 0; i < b; i++){
auto it = lower_bound(all(v[i]), make_pair(e + 1, 0));
if(it != v[i].end()){
auto&[x, ix] = *it;
ans += cnt[ix]; e = d[ix];
//cout << ix << ' ' << cnt[ix] << ' ' << d[ix] << '\n';
}
}
return ans;
}
/*
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> l >> m;
for(int i = 0; i < n; i++) cin >> X[i];
init(n, l, X);
while(m--){
int i, y;
cin >> i >> y;
cout << update(i, y) << '\n';
}
return 0;
}
*/
Compilation message
elephants.cpp: In function 'void go(int)':
elephants.cpp:29:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
29 | auto&[x, ix] = v[k][i];
| ^
elephants.cpp: In function 'int find(int)':
elephants.cpp:58:12: warning: init-statement in selection statements only available with '-std=c++17' or '-std=gnu++17'
58 | if(v[i].size() && (v[i][0].first > X[x] || v[i][0].first == X[x] && v[i][0].second <= X[x]) ret = i;
| ^
elephants.cpp:58:74: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
58 | if(v[i].size() && (v[i][0].first > X[x] || v[i][0].first == X[x] && v[i][0].second <= X[x]) ret = i;
elephants.cpp:58:100: error: expected ';' before 'ret'
58 | if(v[i].size() && (v[i][0].first > X[x] || v[i][0].first == X[x] && v[i][0].second <= X[x]) ret = i;
| ^~~~
| ;
elephants.cpp:59:5: error: expected primary-expression before 'return'
59 | return ret;
| ^~~~~~
elephants.cpp:58:109: error: expected ')' before 'return'
58 | if(v[i].size() && (v[i][0].first > X[x] || v[i][0].first == X[x] && v[i][0].second <= X[x]) ret = i;
| ~ ^
| )
59 | return ret;
| ~~~~~~
elephants.cpp:56:9: warning: unused variable 'ret' [-Wunused-variable]
56 | int ret = 0;
| ^~~
elephants.cpp:60:1: warning: no return statement in function returning non-void [-Wreturn-type]
60 | }
| ^
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:82:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
82 | auto&[x, ix] = *it;
| ^
