#ifndef tabr
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#endif
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
const int MAX_N = 150015;
const int MAX_B = 810;
int B;
int n;
int l;
int upd_cnt;
int x[MAX_N];
int pos[MAX_N];
int jump_cnt[MAX_N];
int jump_pos[MAX_N];
int e[MAX_B][MAX_B];
int sz[MAX_B];
int order[MAX_N];
void init(int n_, int l_, int x_[]) {
n = n_;
l = l_;
B = (n <= 1000 ? 1 : 400);
for (int i = 0; i < n; i++) {
x[i] = x_[i];
}
iota(order, order + n, 0);
}
void build_one(int id) {
sort(e[id], e[id] + sz[id], [&](int i, int j) {
return x[i] < x[j];
});
for (int i = 0; i < sz[id]; i++) {
pos[e[id][i]] = id;
}
for (int i = sz[id] - 1, j = sz[id]; i >= 0; i--) {
while (j > 0 && x[e[id][j - 1]] > x[e[id][i]] + l) {
j--;
}
if (j == sz[id]) {
jump_cnt[e[id][i]] = 1;
jump_pos[e[id][i]] = x[e[id][i]] + l + 1;
} else {
jump_cnt[e[id][i]] = jump_cnt[e[id][j]] + 1;
jump_pos[e[id][i]] = jump_pos[e[id][j]];
}
}
}
void build() {
sort(order, order + n, [&](int i, int j) {
return x[i] < x[j];
});
for (int i = 0; i < B; i++) {
sz[i] = 0;
for (int j = n * i / B; j < n * (i + 1) / B; j++) {
e[i][sz[i]] = order[j];
sz[i]++;
}
build_one(i);
}
}
int update(int i, int y) {
if (n == 1) {
return 1;
}
if (upd_cnt == 0) {
build();
}
upd_cnt++;
if (upd_cnt == n / B - 1) {
upd_cnt = 0;
}
// remove x[i]
for (int j = 0; j < sz[pos[i]] - 1; j++) {
if (e[pos[i]][j] == i) {
e[pos[i]][j] = e[pos[i]][sz[pos[i]] - 1];
break;
}
}
sz[pos[i]]--;
build_one(pos[i]);
// add x[i]
x[i] = y;
for (int id = 0; id < B; id++) {
if (id == B - 1 || x[e[id + 1][0]] > y) {
e[id][sz[id]] = i;
sz[id]++;
build_one(id);
break;
}
}
// answer
int ans = 0;
int now = 0;
for (int id = 0; id < B; id++) {
x[150001] = now;
auto iter = lower_bound(e[id], e[id] + sz[id], 150001, [&](int j, int k) {
return x[j] < x[k];
});
if (iter == e[id] + sz[id]) {
continue;
}
ans += jump_cnt[*iter];
now = jump_pos[*iter];
}
return ans;
}
#ifdef tabr
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n_ = 4;
int l_ = 10;
int x_[10];
x_[0] = 10;
x_[1] = 15;
x_[2] = 17;
x_[3] = 20;
init(n_, l_, x_);
debug(update(2, 16)); // 1
debug(update(1, 25)); // 2
debug(update(3, 35)); // 2
debug(update(0, 38)); // 2
debug(update(2, 0)); // 3
return 0;
}
#endif
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1636 ms |
2496 KB |
Output is correct |
8 |
Correct |
1825 ms |
2636 KB |
Output is correct |
9 |
Correct |
2054 ms |
3376 KB |
Output is correct |
10 |
Correct |
3903 ms |
3372 KB |
Output is correct |
11 |
Correct |
3726 ms |
3376 KB |
Output is correct |
12 |
Correct |
3728 ms |
3376 KB |
Output is correct |
13 |
Correct |
4024 ms |
3376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1636 ms |
2496 KB |
Output is correct |
8 |
Correct |
1825 ms |
2636 KB |
Output is correct |
9 |
Correct |
2054 ms |
3376 KB |
Output is correct |
10 |
Correct |
3903 ms |
3372 KB |
Output is correct |
11 |
Correct |
3726 ms |
3376 KB |
Output is correct |
12 |
Correct |
3728 ms |
3376 KB |
Output is correct |
13 |
Correct |
4024 ms |
3376 KB |
Output is correct |
14 |
Correct |
3080 ms |
2836 KB |
Output is correct |
15 |
Correct |
2697 ms |
2984 KB |
Output is correct |
16 |
Correct |
4438 ms |
3660 KB |
Output is correct |
17 |
Correct |
5461 ms |
4068 KB |
Output is correct |
18 |
Correct |
5883 ms |
4080 KB |
Output is correct |
19 |
Correct |
6556 ms |
4072 KB |
Output is correct |
20 |
Correct |
5504 ms |
4068 KB |
Output is correct |
21 |
Correct |
5954 ms |
4068 KB |
Output is correct |
22 |
Correct |
6401 ms |
4072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1636 ms |
2496 KB |
Output is correct |
8 |
Correct |
1825 ms |
2636 KB |
Output is correct |
9 |
Correct |
2054 ms |
3376 KB |
Output is correct |
10 |
Correct |
3903 ms |
3372 KB |
Output is correct |
11 |
Correct |
3726 ms |
3376 KB |
Output is correct |
12 |
Correct |
3728 ms |
3376 KB |
Output is correct |
13 |
Correct |
4024 ms |
3376 KB |
Output is correct |
14 |
Correct |
3080 ms |
2836 KB |
Output is correct |
15 |
Correct |
2697 ms |
2984 KB |
Output is correct |
16 |
Correct |
4438 ms |
3660 KB |
Output is correct |
17 |
Correct |
5461 ms |
4068 KB |
Output is correct |
18 |
Correct |
5883 ms |
4080 KB |
Output is correct |
19 |
Correct |
6556 ms |
4072 KB |
Output is correct |
20 |
Correct |
5504 ms |
4068 KB |
Output is correct |
21 |
Correct |
5954 ms |
4068 KB |
Output is correct |
22 |
Correct |
6401 ms |
4072 KB |
Output is correct |
23 |
Execution timed out |
9011 ms |
6860 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |