#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int sq = 400;
int X[150015], L;
struct group {
int x[808], p[808], r[808], sz;
void update() {
for(int i=sz-1, j=sz;i>=0;i--) {
while(j > i && x[j-1]-x[i] > L) j--;
if(j == sz) r[i] = x[i], p[i] = 1;
else r[i] = r[j], p[i] = p[j]+1;
}
}
void add(int u) {
x[sz++] = u;
for(int i=sz-1;i>0;i--) if(x[i] < x[i-1]) swap(x[i], x[i-1]);
update();
}
void erase(int u) {
int k = 0;
while(x[k] != u) k++;
for(int i=k+1;i<sz;i++) swap(x[i-1], x[i]);
sz--;
update();
}
} g[404];
int n, cnt, in[150015];
void rebuild() {
}
void init(int N, int L, int X[]) {
::L = L;
for(int i=0;i<N;i++) ::X[i] = X[i], in[i] = i/sq, g[i/sq].add(X[i]);
}
int update(int i, int y) {
g[in[i]].erase(X[i]);
X[i] = y, in[i] = sq-1;
while(in[i] && (!g[in[i]].sz || y < g[in[i]].x[0])) in[i]--;
g[in[i]].add(y);
if(++cnt == sq) rebuild(), cnt = 0;
int ans = 0, R = -1;
for(int i=0;i<sq;i++) if(g[i].sz && R < g[i].x[g[i].sz-1]) {
int s = 0, e = g[i].sz;
while(s <= e) {
int mid = (s+e) >> 1;
if(g[i].x[mid] <= R) s = mid+1;
else e = mid-1;
}
ans += g[i].p[s], R = g[i].r[s]+L;
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |