#include <bits/stdc++.h>
using namespace std;
#include "elephants.h"
const int MAX_N = 150'000, B = 500, INF = 2e9;
int N, L, LIM, X[MAX_N], Y[MAX_N], num[MAX_N], pos[MAX_N], q_;
vector<int> a[B], b[B];
void recalculate(int j) {
auto &c = a[j];
int sz = size(c), pt = sz;
for(int i = sz; --i >= 0; ) {
while(pt && X[c[i]] + L < X[c[pt-1]]) --pt;
num[c[i]] = pt < sz ? num[c[pt]] + 1 : 1;
pos[c[i]] = pt < sz ? pos[c[pt]] : X[c[i]] + L;
}
}
void reset() {
for(int i = 0, j = 0; i < LIM; i++) {
for(int &v : a[i]) pos[j++] = v;
a[i].clear();
b[i].clear();
if(i + 1 == LIM)
assert(j == N);
}
for(int i = 0; i < N; i++) {
Y[pos[i]] = i/B;
a[i/B].push_back(pos[i]);
b[i/B].push_back(X[pos[i]]);
}
for(int i = 0; i < LIM; i++)
recalculate(i);
}
void init(int n, int l, int x[]) {
N = n, L = l, LIM = (N - 1)/B + 1;
for(int i = 0; i < N; i++) {
X[i] = x[i];
a[i/B].push_back(i);
}
reset();
}
int update(int i, int y) {
int l = Y[i];
int p = lower_bound(begin(b[l]), end(b[l]), X[i]) - begin(b[l]);
while(a[l][p] != i) ++p;
a[l].erase(begin(a[l]) + p);
b[l].erase(begin(b[l]) + p);
recalculate(l);
X[i] = y;
for(l = 0; l < LIM; l++)
if(!empty(b[l]) && b[l][0] > X[i]) break;
if(l) --l;
p = lower_bound(begin(b[l]), end(b[l]), X[i]) - begin(b[l]);
Y[i] = l;
a[l].insert(begin(a[l]) + p, i);
b[l].insert(begin(b[l]) + p, X[i]);
recalculate(l);
if(!(++q_ % (B - 2))) reset();
int res = 0, curr = -1;
for(int k = 0; k < LIM; k++) {
if(empty(b[k]) || curr >= b[k].back()) continue;
int j = upper_bound(begin(b[k]), end(b[k]), curr) - begin(b[k]);
res += num[a[k][j]];
curr = pos[a[k][j]];
}
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
568 ms |
1284 KB |
Output is correct |
8 |
Correct |
583 ms |
1476 KB |
Output is correct |
9 |
Correct |
495 ms |
2316 KB |
Output is correct |
10 |
Correct |
479 ms |
2332 KB |
Output is correct |
11 |
Correct |
466 ms |
2324 KB |
Output is correct |
12 |
Correct |
740 ms |
2496 KB |
Output is correct |
13 |
Correct |
470 ms |
2344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
568 ms |
1284 KB |
Output is correct |
8 |
Correct |
583 ms |
1476 KB |
Output is correct |
9 |
Correct |
495 ms |
2316 KB |
Output is correct |
10 |
Correct |
479 ms |
2332 KB |
Output is correct |
11 |
Correct |
466 ms |
2324 KB |
Output is correct |
12 |
Correct |
740 ms |
2496 KB |
Output is correct |
13 |
Correct |
470 ms |
2344 KB |
Output is correct |
14 |
Correct |
582 ms |
1800 KB |
Output is correct |
15 |
Correct |
862 ms |
3620 KB |
Output is correct |
16 |
Correct |
1266 ms |
4388 KB |
Output is correct |
17 |
Correct |
1242 ms |
5152 KB |
Output is correct |
18 |
Correct |
1363 ms |
5328 KB |
Output is correct |
19 |
Correct |
777 ms |
5292 KB |
Output is correct |
20 |
Correct |
1302 ms |
5344 KB |
Output is correct |
21 |
Correct |
1214 ms |
5292 KB |
Output is correct |
22 |
Correct |
745 ms |
4724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
568 ms |
1284 KB |
Output is correct |
8 |
Correct |
583 ms |
1476 KB |
Output is correct |
9 |
Correct |
495 ms |
2316 KB |
Output is correct |
10 |
Correct |
479 ms |
2332 KB |
Output is correct |
11 |
Correct |
466 ms |
2324 KB |
Output is correct |
12 |
Correct |
740 ms |
2496 KB |
Output is correct |
13 |
Correct |
470 ms |
2344 KB |
Output is correct |
14 |
Correct |
582 ms |
1800 KB |
Output is correct |
15 |
Correct |
862 ms |
3620 KB |
Output is correct |
16 |
Correct |
1266 ms |
4388 KB |
Output is correct |
17 |
Correct |
1242 ms |
5152 KB |
Output is correct |
18 |
Correct |
1363 ms |
5328 KB |
Output is correct |
19 |
Correct |
777 ms |
5292 KB |
Output is correct |
20 |
Correct |
1302 ms |
5344 KB |
Output is correct |
21 |
Correct |
1214 ms |
5292 KB |
Output is correct |
22 |
Correct |
745 ms |
4724 KB |
Output is correct |
23 |
Correct |
2803 ms |
11280 KB |
Output is correct |
24 |
Correct |
2967 ms |
11276 KB |
Output is correct |
25 |
Correct |
2172 ms |
11316 KB |
Output is correct |
26 |
Correct |
2916 ms |
11292 KB |
Output is correct |
27 |
Correct |
2878 ms |
11140 KB |
Output is correct |
28 |
Correct |
1994 ms |
5260 KB |
Output is correct |
29 |
Correct |
1968 ms |
5220 KB |
Output is correct |
30 |
Correct |
2011 ms |
5320 KB |
Output is correct |
31 |
Correct |
1989 ms |
5220 KB |
Output is correct |
32 |
Correct |
2125 ms |
10716 KB |
Output is correct |
33 |
Correct |
1979 ms |
10044 KB |
Output is correct |
34 |
Correct |
2281 ms |
11016 KB |
Output is correct |
35 |
Correct |
1996 ms |
11212 KB |
Output is correct |
36 |
Correct |
2130 ms |
10776 KB |
Output is correct |
37 |
Correct |
3149 ms |
12548 KB |
Output is correct |
38 |
Correct |
2271 ms |
9924 KB |
Output is correct |
39 |
Correct |
2241 ms |
11016 KB |
Output is correct |
40 |
Correct |
2328 ms |
9960 KB |
Output is correct |
41 |
Correct |
3825 ms |
11108 KB |
Output is correct |
42 |
Correct |
3876 ms |
11236 KB |
Output is correct |