#include <bits/stdc++.h>
using namespace std;
#define ar2 array<int, 2>
#define lb(v, x) lower_bound(v.begin(), v.end(), x)-v.begin()
const int mx = 1.5e5+5, sq = 555, mBL = mx/sq+5;
int N, L, X[mx], R[mx], mxB, reset; vector<int> blk[mBL]; vector<ar2> dp[mBL]; map<int, int> mp;
void calc(int b){
int sz = blk[b].size(); dp[b].clear(); dp[b].resize(sz);
for (int i = sz-1, p = sz-1; i >= 0; i--){
while (blk[b][p]-blk[b][i] > L) p--;
dp[b][i] = (p == sz-1) ? ar2{1, blk[b][i]+L} : ar2{dp[b][p+1][0]+1, dp[b][p+1][1]};
}
}
void build(){
mxB = 0; blk[mxB].clear();
for (auto i : mp){
if (blk[mxB].size() >= sq) blk[++mxB].clear();
blk[mxB].push_back(i.first);
}for (int i = 0; i <= mxB; i++) calc(i), R[i] = (i == mxB) ? 2e9 : blk[i].back();
}
void upd(int x, bool ins){
int b = 0; while (x > R[b]) b++;
int p = lb(blk[b], x);
ins ? blk[b].insert(blk[b].begin()+p, x) : blk[b].erase(blk[b].begin()+p);
calc(b);
}
int query(){
int ans = 0;
for (int b = 0, x = -1; b <= mxB; b++){
int p = lb(blk[b], x+1);
if (p != blk[b].size()) x = dp[b][p][1], ans += dp[b][p][0];
}return ans;
}
void init(int n, int l, int x[]){
N = n; L = l;
for (int i = 0; i < n; i++) X[i] = x[i], mp[X[i]]++;
build();
}
int update(int i, int y){
if (++reset == sq) build(), reset = 0;
mp[X[i]]--;
if (!mp[X[i]]) upd(X[i], 0), mp.erase(X[i]);
if (!mp[y]) upd(y, 1);
mp[y]++;
X[i] = y; return query();
}
Compilation message
elephants.cpp: In function 'int query()':
elephants.cpp:35:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | if (p != blk[b].size()) x = dp[b][p][1], ans += dp[b][p][0];
| ~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
1 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 |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
283 ms |
1804 KB |
Output is correct |
8 |
Correct |
321 ms |
2420 KB |
Output is correct |
9 |
Correct |
433 ms |
4404 KB |
Output is correct |
10 |
Correct |
311 ms |
4424 KB |
Output is correct |
11 |
Correct |
339 ms |
4452 KB |
Output is correct |
12 |
Correct |
758 ms |
4552 KB |
Output is correct |
13 |
Correct |
327 ms |
4476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
283 ms |
1804 KB |
Output is correct |
8 |
Correct |
321 ms |
2420 KB |
Output is correct |
9 |
Correct |
433 ms |
4404 KB |
Output is correct |
10 |
Correct |
311 ms |
4424 KB |
Output is correct |
11 |
Correct |
339 ms |
4452 KB |
Output is correct |
12 |
Correct |
758 ms |
4552 KB |
Output is correct |
13 |
Correct |
327 ms |
4476 KB |
Output is correct |
14 |
Correct |
239 ms |
2312 KB |
Output is correct |
15 |
Correct |
487 ms |
4344 KB |
Output is correct |
16 |
Correct |
1076 ms |
6624 KB |
Output is correct |
17 |
Correct |
1148 ms |
8352 KB |
Output is correct |
18 |
Correct |
1297 ms |
8388 KB |
Output is correct |
19 |
Correct |
654 ms |
8252 KB |
Output is correct |
20 |
Correct |
1217 ms |
8544 KB |
Output is correct |
21 |
Correct |
1243 ms |
8304 KB |
Output is correct |
22 |
Correct |
615 ms |
7708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
283 ms |
1804 KB |
Output is correct |
8 |
Correct |
321 ms |
2420 KB |
Output is correct |
9 |
Correct |
433 ms |
4404 KB |
Output is correct |
10 |
Correct |
311 ms |
4424 KB |
Output is correct |
11 |
Correct |
339 ms |
4452 KB |
Output is correct |
12 |
Correct |
758 ms |
4552 KB |
Output is correct |
13 |
Correct |
327 ms |
4476 KB |
Output is correct |
14 |
Correct |
239 ms |
2312 KB |
Output is correct |
15 |
Correct |
487 ms |
4344 KB |
Output is correct |
16 |
Correct |
1076 ms |
6624 KB |
Output is correct |
17 |
Correct |
1148 ms |
8352 KB |
Output is correct |
18 |
Correct |
1297 ms |
8388 KB |
Output is correct |
19 |
Correct |
654 ms |
8252 KB |
Output is correct |
20 |
Correct |
1217 ms |
8544 KB |
Output is correct |
21 |
Correct |
1243 ms |
8304 KB |
Output is correct |
22 |
Correct |
615 ms |
7708 KB |
Output is correct |
23 |
Correct |
2898 ms |
18056 KB |
Output is correct |
24 |
Correct |
2936 ms |
18092 KB |
Output is correct |
25 |
Correct |
2269 ms |
17904 KB |
Output is correct |
26 |
Correct |
2382 ms |
17648 KB |
Output is correct |
27 |
Correct |
2527 ms |
17484 KB |
Output is correct |
28 |
Correct |
1348 ms |
5424 KB |
Output is correct |
29 |
Correct |
1295 ms |
5444 KB |
Output is correct |
30 |
Correct |
1347 ms |
5416 KB |
Output is correct |
31 |
Correct |
1307 ms |
5492 KB |
Output is correct |
32 |
Correct |
2160 ms |
17140 KB |
Output is correct |
33 |
Correct |
1539 ms |
18660 KB |
Output is correct |
34 |
Correct |
1979 ms |
17248 KB |
Output is correct |
35 |
Correct |
948 ms |
17528 KB |
Output is correct |
36 |
Correct |
75 ms |
7656 KB |
Output is correct |
37 |
Correct |
1438 ms |
17452 KB |
Output is correct |
38 |
Correct |
1952 ms |
16248 KB |
Output is correct |
39 |
Correct |
2237 ms |
17320 KB |
Output is correct |
40 |
Correct |
2102 ms |
16352 KB |
Output is correct |
41 |
Correct |
4133 ms |
17492 KB |
Output is correct |
42 |
Correct |
4274 ms |
17820 KB |
Output is correct |