#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=150050,inf=1e9;
int koren=390;
int n,a[N],L,res,nq,dp[400][2500],poslednji[400][2500];
vector<int>A[N];
multiset<int>b;
void Calcblok(int i){
if(A[i].empty()) return;
for(int j=A[i].size()-1,k=A[i].size()-1;j>=0;j--){
while(k>=1 && A[i][j]+L<A[i][k-1]) k--;
if(A[i][j]+L>=A[i].back()){
dp[i][j]=1;
poslednji[i][j]=j;
}
else{
dp[i][j]=1+dp[i][k];
poslednji[i][j]=poslednji[i][k];
}
}
}
void Erase(int x){
for(int i=0;i<koren;i++){
if(A[i].empty()) continue;
if(A[i][0]<=x && x<=A[i].back()){
int ind=A[i].size();
for(int j=0;j<A[i].size();j++) if(A[i][j]==x) ind=j;
while(ind+1<A[i].size()){swap(A[i][ind],A[i][ind+1]);ind++;}
A[i].pop_back();
Calcblok(i);
break;
}
}
}
void Insert(int x){
for(int i=0;i<koren;i++){
if(A[i].empty()) break;
int l=0,r=inf;
if(i>=1 && !A[i-1].empty()) l=A[i-1].back();
if(!A[i+1].empty()) r=A[i+1][0];
if(l<=x && x<=r){
A[i].pb(x);
int ind=A[i].size()-1;
while(ind>=1 && A[i][ind]<A[i][ind-1]){swap(A[i][ind],A[i][ind-1]);ind--;}
Calcblok(i);
break;
}
}
}
void Calc(){
for(int i=0;i<koren;i++) A[i].clear();
int I=0;
for(auto i=b.begin();i!=b.end();i++,I++) A[I/koren].pb(*i);
for(int i=0;i<koren;i++) Calcblok(i);
}
int Resi(){
int res=0;
int x=A[0][0];
for(int i=0;i<koren;i++){
if(A[i].empty()) continue;
if(x<=A[i].back()){
int ind=0;
for(int j=A[i].size()-1;j>=0;j--) if(A[i][j]>=x) ind=j;
res+=dp[i][ind];
x=A[i][poslednji[i][ind]]+L+1;
}
}
return res;
}
void init(int N1, int L1, int X[]){
n = N1;
for(int i=0;i<n;i++) a[i]=X[i];
for(int i=0;i<n;i++) b.insert(a[i]);
L=L1;
for(int i=0;i<N;i++) A[i].reserve(2*koren+10);
Calc();
}
int update(int qind, int y){
Erase(a[qind]);
b.erase(b.find(a[qind]));
a[qind]=y;
b.insert(a[qind]);
Insert(a[qind]);
nq++;
if(nq>=koren) {Calc();nq-=koren;}
return Resi();
}
Compilation message
elephants.cpp: In function 'void Erase(int)':
elephants.cpp:33:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int j=0;j<A[i].size();j++) if(A[i][j]==x) ind=j;
| ~^~~~~~~~~~~~
elephants.cpp:34:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | while(ind+1<A[i].size()){swap(A[i][ind],A[i][ind+1]);ind++;}
| ~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
90 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
90 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
90 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
90 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
90 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
