//#include "elephants.h"
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int maxn = 2e5 + 5, SQ = 700;
int n, b[maxn], p[maxn], c[maxn], Len, Bl, en[maxn];
vector<int> x[SQ];
void calc(vector<int> v) {
int l = (int)v.size(); --l;
for(int j = (int)v.size() - 1; j >= 0; j--) {
while(p[v[j]] + Len < p[v[l]]) --l;
if(l == (int)v.size() - 1) c[v[j]] = 1, en[v[j]] = p[v[j]] + Len;
else c[v[j]] = c[v[l + 1]] + 1, en[v[j]] = en[v[l + 1]];
}
}
void init(int m, int l, int a[])
{ n = m; Len = l;
for(int i = 0; i < n; i++) p[i] = a[i];
Bl = min(n, 700);
for(int i = 0; i < n; i++) {
x[i / Bl].push_back(i);
b[i] = i / Bl;
}
for(int i = 0; i <= (n - 1) / Bl; i++) calc(x[i]);
}
int update(int id, int y)
{
for(int i = 0; i < x[b[id]].size(); i++) {
if(x[b[id]][i] == id) {
vector<int> v;
for(int j = 0; j < i; j++) v.push_back(x[b[id]][j]);
for(int j = i + 1; j < x[b[id]].size(); j++) v.push_back(x[b[id]][j]);
x[b[id]] = v;
calc(x[b[id]]);
break;
}
}
int last = 2e9, bl = (n - 1) / Bl;
for(int i = (n - 1) / Bl; i >= 0; i--) {
if(last >= y) {
bl = i;
}
if(x[i].size()) last = p[x[i][0]];
}
b[id] = bl;
vector<int> v;
for(int i = 0; i < x[bl].size(); i++) {
if(p[x[bl][i]] >= y) break;
v.push_back(x[bl][i]);
}
v.push_back(id);
for(int i = 0; i < x[bl].size(); i++) {
if(p[x[bl][i]] >= y) v.push_back(x[bl][i]);
}
x[bl] = v;
p[id] = y;
int ff = 0;
for(int i = 0; i <= (n - 1) / Bl; i++) {
if((!x[i].size() && i < (n - 1) / Bl) || x[i].size() >= 2 * Bl) {
ff = 1;
}
}
if(ff) {
vector<int> v;
for(int i = 0; i <= (n - 1) / Bl; i++) {
for(int j = 0; j < x[i].size(); j++) {
v.push_back(x[i][j]);
}
x[i].clear();
}
for(int i = 0; i < n; i++) x[i / Bl].push_back(v[i]), b[v[i]] = i / Bl;
for(int i = 0; i <= (n - 1) / Bl; i++) calc(x[i]);
} else calc(x[bl]);
int cur = x[0][0];
int ans = 0;
while(true) {
ans += c[cur];
int l = b[cur] + 1, r = (n - 1) / Bl, nxt = -1;
while(l <= r) {
int mid = (l + r) / 2;
if(!x[mid].size()) {
r = mid - 1; continue;
}
if(p[x[mid].back()] > en[cur]) nxt = mid, r = mid - 1;
else l = mid + 1;
}
if(nxt == -1) break;
l = 0, r = x[nxt].size(); r--;
int b = 0;
while(l <= r) {
int mid = (l + r) / 2;
if(p[x[nxt][mid]] > en[cur]) b = mid, r = mid - 1;
else l = mid + 1;
}
cur = x[nxt][b];
}
return ans;
}
Compilation message
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int i = 0; i < x[b[id]].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
elephants.cpp:35:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int j = i + 1; j < x[b[id]].size(); j++) v.push_back(x[b[id]][j]);
| ~~^~~~~~~~~~~~~~~~~
elephants.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i = 0; i < x[bl].size(); i++) {
| ~~^~~~~~~~~~~~~~
elephants.cpp:55:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(int i = 0; i < x[bl].size(); i++) {
| ~~^~~~~~~~~~~~~~
elephants.cpp:62:56: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
62 | if((!x[i].size() && i < (n - 1) / Bl) || x[i].size() >= 2 * Bl) {
| ~~~~~~~~~~~~^~~~~~~~~
elephants.cpp:69:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int j = 0; j < x[i].size(); j++) {
| ~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
806 ms |
1260 KB |
Output is correct |
8 |
Correct |
791 ms |
1388 KB |
Output is correct |
9 |
Correct |
896 ms |
2216 KB |
Output is correct |
10 |
Correct |
762 ms |
2704 KB |
Output is correct |
11 |
Correct |
834 ms |
2812 KB |
Output is correct |
12 |
Correct |
1398 ms |
2668 KB |
Output is correct |
13 |
Correct |
845 ms |
2792 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
806 ms |
1260 KB |
Output is correct |
8 |
Correct |
791 ms |
1388 KB |
Output is correct |
9 |
Correct |
896 ms |
2216 KB |
Output is correct |
10 |
Correct |
762 ms |
2704 KB |
Output is correct |
11 |
Correct |
834 ms |
2812 KB |
Output is correct |
12 |
Correct |
1398 ms |
2668 KB |
Output is correct |
13 |
Correct |
845 ms |
2792 KB |
Output is correct |
14 |
Correct |
1142 ms |
1880 KB |
Output is correct |
15 |
Correct |
1177 ms |
1784 KB |
Output is correct |
16 |
Correct |
1914 ms |
2448 KB |
Output is correct |
17 |
Correct |
2012 ms |
3856 KB |
Output is correct |
18 |
Correct |
2110 ms |
3804 KB |
Output is correct |
19 |
Correct |
1493 ms |
3780 KB |
Output is correct |
20 |
Correct |
2071 ms |
3744 KB |
Output is correct |
21 |
Correct |
2028 ms |
3852 KB |
Output is correct |
22 |
Correct |
1538 ms |
3772 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
806 ms |
1260 KB |
Output is correct |
8 |
Correct |
791 ms |
1388 KB |
Output is correct |
9 |
Correct |
896 ms |
2216 KB |
Output is correct |
10 |
Correct |
762 ms |
2704 KB |
Output is correct |
11 |
Correct |
834 ms |
2812 KB |
Output is correct |
12 |
Correct |
1398 ms |
2668 KB |
Output is correct |
13 |
Correct |
845 ms |
2792 KB |
Output is correct |
14 |
Correct |
1142 ms |
1880 KB |
Output is correct |
15 |
Correct |
1177 ms |
1784 KB |
Output is correct |
16 |
Correct |
1914 ms |
2448 KB |
Output is correct |
17 |
Correct |
2012 ms |
3856 KB |
Output is correct |
18 |
Correct |
2110 ms |
3804 KB |
Output is correct |
19 |
Correct |
1493 ms |
3780 KB |
Output is correct |
20 |
Correct |
2071 ms |
3744 KB |
Output is correct |
21 |
Correct |
2028 ms |
3852 KB |
Output is correct |
22 |
Correct |
1538 ms |
3772 KB |
Output is correct |
23 |
Correct |
4072 ms |
6032 KB |
Output is correct |
24 |
Correct |
4319 ms |
5912 KB |
Output is correct |
25 |
Correct |
3851 ms |
5908 KB |
Output is correct |
26 |
Correct |
4008 ms |
7544 KB |
Output is correct |
27 |
Correct |
4839 ms |
7592 KB |
Output is correct |
28 |
Correct |
3474 ms |
2400 KB |
Output is correct |
29 |
Correct |
3438 ms |
2332 KB |
Output is correct |
30 |
Correct |
3537 ms |
2344 KB |
Output is correct |
31 |
Correct |
3435 ms |
2432 KB |
Output is correct |
32 |
Correct |
4137 ms |
7652 KB |
Output is correct |
33 |
Correct |
2940 ms |
7556 KB |
Output is correct |
34 |
Correct |
3789 ms |
7672 KB |
Output is correct |
35 |
Correct |
3880 ms |
7944 KB |
Output is correct |
36 |
Correct |
3842 ms |
7600 KB |
Output is correct |
37 |
Correct |
4944 ms |
6008 KB |
Output is correct |
38 |
Correct |
4380 ms |
7584 KB |
Output is correct |
39 |
Correct |
4513 ms |
7832 KB |
Output is correct |
40 |
Correct |
4952 ms |
7672 KB |
Output is correct |
41 |
Correct |
5600 ms |
7584 KB |
Output is correct |
42 |
Correct |
5773 ms |
7536 KB |
Output is correct |