#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=2e5+5,MAX=1e9+5;
int n,k,arr[mxn],sz,block,loc[mxn],pos[mxn],tmr;
bool cmp(int i,int j){
return arr[i]<arr[j];
}
struct st{
vector<vector<int>>vt,last,dis;
void build(){
vt.clear(),last.clear(),dis.clear();
vector<int>p;
for(int i=1;i<=n;i++){
p.pb(i);
}
sort(all(p),cmp);
int sz=sqrt(n);
int idx=0,say=0;
while(idx<n){
say++;
if(say==1){
vt.pb({});
vt.back().pb(p[idx]);
loc[p[idx]]=vt.size()-1;
}
else{
vt.back().pb(p[idx]);
loc[p[idx]]=vt.size()-1;
}
idx++;
if(say>=sz) say=0;
}
for(int id=0;id<vt.size();id++){
vector<int>vx(sz*10+5);
last.pb(vx);
dis.pb(vx);
int idx=vt[id].size()-1;
for(int i=vt[id].size()-1;i>=0;i--){
while(idx-1>=0&&arr[vt[id][i]]+k<arr[vt[id][idx-1]]){
idx--;
}
if(arr[vt[id][i]]+k>=arr[vt[id][idx]]){
last[id][i]=arr[vt[id][i]]+k+1;
dis[id][i]=1;
}
else{
last[id][i]=last[id][idx];
dis[id][i]=dis[id][idx]+1;
}
}
}
}
int query(){
int left=-5;
int ans=0;
for(int id=0;id<vt.size();id++){
int l=0,r=vt[id].size()-1;
int res=-1;
while(l<=r){
int m=(l+r)/2;
if(arr[vt[id][m]]>=left){
r=m-1;
res=m;
}
else{
l=m+1;
}
}
if(res==-1) continue;
left=last[id][res];
ans+=dis[id][res];
}
return ans;
}
void del(int idx){
int row=loc[idx];
for(int i=0;i<vt[row].size();i++){
if(vt[row][i]==idx){
vt[row].erase(vt[row].begin()+i);
break;
}
}
int id=row;
idx=vt[id].size()-1;
for(int i=vt[id].size()-1;i>=0;i--){
while(idx-1>=0&&arr[vt[id][i]]+k<arr[vt[id][idx-1]]){
idx--;
}
if(arr[vt[id][i]]+k>=arr[vt[id][idx]]){
last[id][i]=arr[vt[id][i]]+k+1;
dis[id][i]=1;
}
else{
last[id][i]=last[id][idx];
dis[id][i]=dis[id][idx]+1;
}
}
}
void add(int idx){
int row=0;
for(int i=vt.size()-1;i>=0;i--){
if(arr[vt[i][0]]<=arr[idx]){
row=i;
break;
}
}
loc[idx]=row;
bool ok=true;
for(int i=0;i<vt[row].size();i++){
if(arr[vt[row][i]]>arr[idx]){
vt[row].insert(vt[row].begin()+i,idx);
ok=false;
break;
}
}
if(ok){
vt[row].pb(idx);
}
int id=row;
idx=vt[id].size()-1;
for(int i=vt[id].size()-1;i>=0;i--){
while(idx-1>=0&&arr[vt[id][i]]+k<arr[vt[id][idx-1]]){
idx--;
}
if(arr[vt[id][i]]+k>=arr[vt[id][idx]]){
last[id][i]=arr[vt[id][i]]+k+1;
dis[id][i]=1;
}
else{
last[id][i]=last[id][idx];
dis[id][i]=dis[id][idx]+1;
}
}
}
};
st data1;
void init(int N, int L, int X[])
{
n=N,k=L;
for(int i=1;i<=n;i++){
arr[i]=X[i-1];
}
tmr=max((int)sqrt(n)-1,1);
}
int update(int i, int val)
{
arr[i+1]=val;
tmr--;
if(tmr==0){
data1.build();
tmr=max((int)sqrt(n),1);
}
else{
data1.del(i+1);
arr[i+1]=val;
data1.add(i+1);
}
return data1.query();
}
/*
g++ elephants.cpp grader.cpp ; .\a.exe
10 10 0
1 3 7 15 27 37 46 90 98 100
4 10 5
10 15 17 20
2 16 1
1 25 2
3 25 2
0 38 2
2 0 3
*/
Compilation message
elephants.cpp: In member function 'void st::build()':
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 id=0;id<vt.size();id++){
| ~~^~~~~~~~~~
elephants.cpp: In member function 'int st::query()':
elephants.cpp:68:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int id=0;id<vt.size();id++){
| ~~^~~~~~~~~~
elephants.cpp: In member function 'void st::del(int)':
elephants.cpp:89:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for(int i=0;i<vt[row].size();i++){
| ~^~~~~~~~~~~~~~~
elephants.cpp: In member function 'void st::add(int)':
elephants.cpp:121:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(int i=0;i<vt[row].size();i++){
| ~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
