#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
// #include "camera.h"
using namespace std;
constexpr int K = 150;
constexpr int T = 12;
int curr = 0;
int loc[70005];
int old[70005];
set<pair<int, int>> batch, all, extra;
bool seen[70005];
int lift[T][70005];
int N, L;
inline void calc() {
vector<pair<int, int>> order(N);
for (int i = 0; i < N; i ++) order[i] = {loc[i], i};
sort(order.begin(), order.end());
for (int i = 0; i < N; i ++) {
old[i] = loc[i];
int t = lower_bound(order.begin(), order.end(), make_pair(order[i].first + L + 1, -1)) - order.begin();
lift[0][order[i].second] = N;
if (t < N) lift[0][order[i].second] = order[t].second;
}
lift[0][N] = N;
for (int i = 1; i < T; i ++) {
for (int j = 0; j <= N; j ++) {
lift[i][j] = lift[i-1][lift[i-1][j]];
}
}
for (auto [a, b]:batch) seen[b] = 0;
batch.clear();
extra.clear();
extra.insert({2e9+5, N});
batch.insert({2e9+5, N});
}
void init(int n, int l, int X[]) {
N = n, L = l;
for (int i = 0; i < N; i ++) {
loc[i] = X[i];
old[i] = X[i];
lift[0][i] = lower_bound(X, X+N, loc[i] + L + 1) - X;
all.insert({X[i], i});
}
old[N] = 2e9+5;
loc[N] = 2e9+5;
all.insert({2e9+5, N});
lift[0][N] = N;
for (int i = 1; i < T; i ++) {
for (int j = 0; j <= N; j ++) {
lift[i][j] = lift[i-1][lift[i-1][j]];
}
}
extra.insert({2e9+5, N});
batch.insert({2e9+5, N});
}
int update(int i, int y /*, int debug = 0*/) {
all.erase({loc[i], i});
all.insert({y, i});
if (seen[i]) {
batch.erase({loc[i], i});
batch.insert({y, i});
} else {
seen[i] = 1;
extra.insert({old[i], i});
batch.insert({y, i});
}
loc[i] = y;
if (batch.size() == K) calc();
auto it = batch.begin(), it2 = extra.begin();
int upto = all.begin()->second, ans = 0;
while (upto < N) {
// see how far it can be placed
if (upto != it->second) {
// there are some disruptor events
for (int i = T-1; i >= 0; i --) if (old[lift[i][upto]] < min(it2->first, it->first)) {
upto = lift[i][upto];
ans += (1 << i);
}
}
if (upto == N) {
return ans;
}
// forced placements
do {
ans ++;
upto = all.lower_bound(make_pair(loc[upto] + L + 1, -1))->second;
while (it->first < loc[upto]) it = next(it);
while (it2->first < loc[upto]) it2 = next(it2);
} while (upto < N and it->first <= loc[upto] + L + 1);
}
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... |