#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int sq = 3;
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() {
vector<array<int, 2>> p(N);
for(int i=0;i<N;i++) p[i] = {X[i], i};
sort(p.begin(), p.end());
for(int i=0;i<sq;i++) g[i].sz = 0;
for(int i=0;i<N;i++) in[p[i][1]] = i/sq, g[i/sq].add(p[i][0]);
}
void init(int N, int L, int X[]) {
::L = L, ::N = N, memcpy(::X, X, sizeof(int)*N);
rebuild();
}
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-1;
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... |