#include "elephants.h"
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int maxn = 2e5 + 5, SQ = 400;
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 = sqrt(n);
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(); i++) {
v.push_back(x[i][j]);
}
}
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(); i++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
