#include "elephants.h"
#include "bits/stdc++.h"
using namespace std;
const int B = 450;
int n, l;
int tot, qc;
vector<int> a;
vector<int> bucket;
vector<int> nxt, cnt;
vector<int> in_bucket[B];
void calc(int bucket_num) {
int m = in_bucket[bucket_num].size();
if (m == 0) {
return;
}
int p = m - 1;
for (int i = m - 1; i >= 0; --i) {
int cur = in_bucket[bucket_num][i];
while (a[in_bucket[bucket_num][p]] - a[cur] > l) {
p--;
}
if (p == m - 1) {
cnt[cur] = 1;
nxt[cur] = a[cur] + l;
} else {
nxt[cur] = nxt[in_bucket[bucket_num][p + 1]];
cnt[cur] = cnt[in_bucket[bucket_num][p + 1]] + 1;
}
}
}
void init(int N_, int L, int X[]) {
n = N_, l = L;
a.resize(n);
cnt.resize(n);
nxt.resize(n);
bucket.resize(n);
tot = (n - 1) / B;
for (int i = 0; i < n; ++i) {
a[i] = X[i];
}
for (int i = 0; i < n; ++i) {
in_bucket[i / B].push_back(i);
bucket[i] = i / B;
}
for (int i = 0; i <= tot; ++i) {
calc(i);
}
}
int search(int x, int st) {
for (int i = st; i <= tot; ++i) {
if (!in_bucket[i].empty() && a[in_bucket[i].back()] > x) {
for (int j : in_bucket[i]) {
if (a[j] > x) {
return j;
}
}
}
}
return -1;
}
int query() {
int ret = 0;
int x = -1;
int la = 0;
while (true) {
int nb = search(x, la);
if (nb == -1) {
break;
}
la = bucket[nb];
x = nxt[nb];
ret += cnt[nb];
}
return ret;
}
void rebuild() {
qc = 0;
vector<int> p;
for (int i = 0; i <= tot; ++i) {
for (int j : in_bucket[i]) {
p.push_back(j);
}
in_bucket[i].clear();
}
for (int i = 0; i < n; ++i) {
in_bucket[i / B].push_back(p[i]);
bucket[p[i]] = i / B;
}
for (int i = 0; i <= tot; ++i) {
calc(i);
}
}
int update(int i, int y) {
qc++;
if (qc == B) {
rebuild();
}
int b1 = bucket[i];
in_bucket[b1].erase(find(in_bucket[b1].begin(), in_bucket[b1].end(), i));
int b2 = search(y, 0);
if (b2 == -1) {
b2 = tot;
} else {
b2 = bucket[b2];
}
bucket[i] = b2;
bool f = false;
for (int j = 0; j < (int) in_bucket[b2].size(); ++j) {
if (a[in_bucket[b2][j]] > y) {
f = true;
in_bucket[b2].insert(in_bucket[b2].begin() + j, i);
break;
}
}
if (!f) {
in_bucket[b2].push_back(i);
}
a[i] = y;
calc(b1);
calc(b2);
return query();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
1 ms |
6744 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
1 ms |
6744 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 KB |
Output is correct |
6 |
Correct |
1 ms |
6492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
1 ms |
6744 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 KB |
Output is correct |
6 |
Correct |
1 ms |
6492 KB |
Output is correct |
7 |
Correct |
186 ms |
9456 KB |
Output is correct |
8 |
Correct |
197 ms |
9420 KB |
Output is correct |
9 |
Correct |
250 ms |
10276 KB |
Output is correct |
10 |
Correct |
310 ms |
10384 KB |
Output is correct |
11 |
Correct |
321 ms |
10268 KB |
Output is correct |
12 |
Correct |
521 ms |
10384 KB |
Output is correct |
13 |
Correct |
405 ms |
10272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
1 ms |
6744 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 KB |
Output is correct |
6 |
Correct |
1 ms |
6492 KB |
Output is correct |
7 |
Correct |
186 ms |
9456 KB |
Output is correct |
8 |
Correct |
197 ms |
9420 KB |
Output is correct |
9 |
Correct |
250 ms |
10276 KB |
Output is correct |
10 |
Correct |
310 ms |
10384 KB |
Output is correct |
11 |
Correct |
321 ms |
10268 KB |
Output is correct |
12 |
Correct |
521 ms |
10384 KB |
Output is correct |
13 |
Correct |
405 ms |
10272 KB |
Output is correct |
14 |
Correct |
301 ms |
9384 KB |
Output is correct |
15 |
Correct |
310 ms |
9512 KB |
Output is correct |
16 |
Correct |
886 ms |
10420 KB |
Output is correct |
17 |
Correct |
906 ms |
11188 KB |
Output is correct |
18 |
Correct |
994 ms |
11212 KB |
Output is correct |
19 |
Correct |
425 ms |
11016 KB |
Output is correct |
20 |
Correct |
924 ms |
11148 KB |
Output is correct |
21 |
Correct |
884 ms |
11152 KB |
Output is correct |
22 |
Correct |
801 ms |
11028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
1 ms |
6744 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 KB |
Output is correct |
6 |
Correct |
1 ms |
6492 KB |
Output is correct |
7 |
Correct |
186 ms |
9456 KB |
Output is correct |
8 |
Correct |
197 ms |
9420 KB |
Output is correct |
9 |
Correct |
250 ms |
10276 KB |
Output is correct |
10 |
Correct |
310 ms |
10384 KB |
Output is correct |
11 |
Correct |
321 ms |
10268 KB |
Output is correct |
12 |
Correct |
521 ms |
10384 KB |
Output is correct |
13 |
Correct |
405 ms |
10272 KB |
Output is correct |
14 |
Correct |
301 ms |
9384 KB |
Output is correct |
15 |
Correct |
310 ms |
9512 KB |
Output is correct |
16 |
Correct |
886 ms |
10420 KB |
Output is correct |
17 |
Correct |
906 ms |
11188 KB |
Output is correct |
18 |
Correct |
994 ms |
11212 KB |
Output is correct |
19 |
Correct |
425 ms |
11016 KB |
Output is correct |
20 |
Correct |
924 ms |
11148 KB |
Output is correct |
21 |
Correct |
884 ms |
11152 KB |
Output is correct |
22 |
Correct |
801 ms |
11028 KB |
Output is correct |
23 |
Correct |
1798 ms |
17732 KB |
Output is correct |
24 |
Correct |
1951 ms |
22764 KB |
Output is correct |
25 |
Correct |
1370 ms |
22624 KB |
Output is correct |
26 |
Correct |
1715 ms |
22776 KB |
Output is correct |
27 |
Correct |
1694 ms |
22460 KB |
Output is correct |
28 |
Correct |
814 ms |
16000 KB |
Output is correct |
29 |
Correct |
836 ms |
16212 KB |
Output is correct |
30 |
Correct |
812 ms |
15980 KB |
Output is correct |
31 |
Correct |
795 ms |
16004 KB |
Output is correct |
32 |
Correct |
2575 ms |
22208 KB |
Output is correct |
33 |
Correct |
1185 ms |
21416 KB |
Output is correct |
34 |
Correct |
2393 ms |
22560 KB |
Output is correct |
35 |
Correct |
1099 ms |
22656 KB |
Output is correct |
36 |
Correct |
1127 ms |
22256 KB |
Output is correct |
37 |
Correct |
2502 ms |
23280 KB |
Output is correct |
38 |
Correct |
3632 ms |
21696 KB |
Output is correct |
39 |
Correct |
1442 ms |
22480 KB |
Output is correct |
40 |
Correct |
5218 ms |
21528 KB |
Output is correct |
41 |
Correct |
2917 ms |
22392 KB |
Output is correct |
42 |
Correct |
2951 ms |
22596 KB |
Output is correct |