#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+5;
const int INF = 1e9+5;
int arr[MAXN],n,l,pos[MAXN]; //bucket i is in
bool cmp(int x, int y){
return arr[x]<arr[y];
}
struct bucket{
vector<vector<int>> vec,nxt,fotos;
void build(){
vec.clear(); nxt.clear(); fotos.clear();
vector<int> ind;
for(int i = 1;i<=n;++i) ind.push_back(i);
sort(ind.begin(),ind.end(),cmp);
int id = 0, b = 0;
while(id < n){
b++;
if(b == 1) vec.push_back({});
vec.back().push_back(ind[id]);
pos[ind[id]] = vec.size()-1;
id++;
if(b >= 500) b = 0;
}
for(int i = 0;i<vec.size();++i){
vector<int> v(2505);
fotos.push_back(v); nxt.push_back(v);
int cur = vec[i].size()-1;
for(int j = vec[i].size()-1;j >= 0;--j){
while(cur > 0 && arr[vec[i][cur-1]] > arr[vec[i][j]]+l) cur--;
if(arr[vec[i][cur]] <= arr[vec[i][j]]+l){
fotos[i][j] = 1;
nxt[i][j] = arr[vec[i][j]]+l+1;
}
else{
fotos[i][j] = fotos[i][cur]+1;
nxt[i][j] = nxt[i][cur];
}
}
}
}
int query(){
int lo = -INF, ans = 0;
for(int i = 0;i<vec.size();++i){ //find the first position that is >= lo
int l = 0, r = vec[i].size()-1, erg = -1;
while(l <= r){
int mid = (l+r)/2;
if(arr[vec[i][mid]] >= lo){
erg = mid;
r = mid-1;
}
else{
l = mid+1;
}
}
if(erg == -1) continue;
ans += fotos[i][erg]; lo = nxt[i][erg];
}
return ans;
}
void ins(int id){
int bnum = 0;
for(int i = vec.size()-1;i>=0;--i){
if(arr[vec[i][0]] <= arr[id]){
bnum = i;
break;
}
}
bool good = false;
for(int i = 0;i<vec[bnum].size();++i){
if(vec[bnum][i] > arr[id]){
vec[bnum].insert(vec[bnum].begin()+i,id);
good = true;
break;
}
}
pos[id] = bnum;
if(!good) vec[bnum].push_back(id);
int i = bnum;
int cur = vec[i].size()-1;
for(int j = vec[i].size()-1;j >= 0;--j){
while(cur > 0 && arr[vec[i][cur-1]] > arr[vec[i][j]]+l) cur--;
if(arr[vec[i][cur]] <= arr[vec[i][j]]+l){
fotos[i][j] = 1;
nxt[i][j] = arr[vec[i][j]]+l+1;
}
else{
fotos[i][j] = fotos[i][cur]+1;
nxt[i][j] = nxt[i][cur];
}
}
}
void del(int id){
int bnum = pos[id];
for(int i = 0;i<vec[bnum].size();++i){
if(vec[bnum][i] == id){
vec[bnum].erase(vec[bnum].begin()+i);
break;
}
}
int i = bnum;
int cur = vec[i].size()-1;
for(int j = vec[i].size()-1;j >= 0;--j){
while(cur > 0 && arr[vec[i][cur-1]] > arr[vec[i][j]]+l) cur--;
if(arr[vec[i][cur]] <= arr[vec[i][j]]+l){
fotos[i][j] = 1;
nxt[i][j] = arr[vec[i][j]]+l+1;
}
else{
fotos[i][j] = fotos[i][cur]+1;
nxt[i][j] = nxt[i][cur];
}
}
}
};
int curq; bucket eimer;
void init(int N, int L, int X[]){
n = N; l = L;
for(int i = 1;i<=N;++i) arr[i] = X[i-1];
eimer.build();
curq = 490;
}
int update(int i, int y){
arr[i+1] = y;
curq--;
if(curq == 0){
eimer.build();
curq = 490;
}
else{
eimer.del(i+1);
arr[i+1] = y;
eimer.ins(i+1);
}
return eimer.query();
}
Compilation message
elephants.cpp: In member function 'void bucket::build()':
elephants.cpp:26:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for(int i = 0;i<vec.size();++i){
| ~^~~~~~~~~~~
elephants.cpp: In member function 'int bucket::query()':
elephants.cpp:45:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int i = 0;i<vec.size();++i){ //find the first position that is >= lo
| ~^~~~~~~~~~~
elephants.cpp: In member function 'void bucket::ins(int)':
elephants.cpp:71:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int i = 0;i<vec[bnum].size();++i){
| ~^~~~~~~~~~~~~~~~~
elephants.cpp: In member function 'void bucket::del(int)':
elephants.cpp:96:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int i = 0;i<vec[bnum].size();++i){
| ~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
