#include "elephants.h"
#include <math.h>
#include <algorithm>
using namespace std;
int N, L, BucketNum, BucketLimit, Bucket[2][400][800], Size[400], Loc[150000][2];
int Next[400][800], Cnt[400][800], Temp[150000][2], Num;
void GiveInfo(int X) {
int BucketNow=Size[X];
Next[X][Size[X]-1]=Bucket[0][X][Size[X]-1]+L;
Cnt[X][Size[X]-1]=1;
for(int i=Size[X]-2 ; i>=0 ; i--) {
while(Bucket[0][X][i]+L<Bucket[0][X][BucketNow-1]) BucketNow--;
if(BucketNow==Size[X]) {
Next[X][i]=Bucket[0][X][i]+L;
Cnt[X][i]=1;
}
else {
Next[X][i]=Next[X][BucketNow];
Cnt[X][i]=Cnt[X][BucketNow]+1;
}
}
}
void ReArrange(void) {
int TempSize=0, BucketNow=0;
for(int i=0 ; i<BucketNum ; i++) {
for(int j=0 ; j<Size[i] ; j++) {
Temp[TempSize][0]=Bucket[0][i][j];
Temp[TempSize][1]=Bucket[1][i][j];
TempSize++;
}
Size[i]=0;
}
for(int i=0 ; i<N ; i++) {
Bucket[0][BucketNow][Size[BucketNow]]=Temp[i][0];
Bucket[1][BucketNow][Size[BucketNow]]=Temp[i][1];
Loc[Temp[i][1]][0]=BucketNow;
Loc[Temp[i][1]][1]=Size[BucketNow];
Size[BucketNow]++;
if(Size[BucketNow]==BucketLimit)
BucketNow++;
}
for(int i=0 ; i<BucketNum ; i++)
GiveInfo(i);
}
void init(int N_, int L_, int X[]) {
N=N_;
L=L_;
BucketNum=BucketLimit=sqrt(N);
if(BucketNum*BucketNum!=N)
BucketNum++;
for(int i=0 ; i<N ; i++) {
Bucket[0][0][Size[0]]=X[i];
Bucket[1][0][Size[0]]=i;
Loc[i][0]=0;
Loc[i][1]=Size[0];
Size[0]++;
}
ReArrange();
}
void Delete(int Key) {
int X=Loc[Key][0], Y=Loc[Key][1];
for(int i=Y+1 ; i<Size[X] ; i++) {
Bucket[0][X][i-1]=Bucket[0][X][i];
Bucket[1][X][i-1]=Bucket[1][X][i];
Loc[Bucket[1][X][i]][0]=X;
Loc[Bucket[1][X][i]][1]=i-1;
}
Size[X]--;
GiveInfo(X);
}
void Insert(int X, int Y) {
int Key1, Key2;
for(Key1=0 ; Key1<BucketNum-1 && X>Bucket[0][Key1][Size[Key1]-1] ; Key1++);
for(Key2=0 ; Key2<Size[Key1] && X>Bucket[0][Key1][Key2] ; Key2++);
for(int i=Size[Key1] ; i>=Key2+1 ; i--) {
Bucket[0][Key1][i]=Bucket[0][Key1][i-1];
Bucket[1][Key1][i]=Bucket[1][Key1][i-1];
Loc[Bucket[Key1][i][1]][0]=Key1;
Loc[Bucket[Key1][i][1]][1]=i;
}
Bucket[0][Key1][Key2]=X;
Bucket[1][Key1][Key2]=Y;
Loc[Y][0]=Key1;
Loc[Y][1]=Key2;
Size[Key1]++;
GiveInfo(Key1);
}
int FindAns(void) {
int Length=-1, Key, Ans=0;
for(int i=0 ; i<BucketNum ; i++) {
Key=lower_bound(Bucket[0][i],Bucket[0][i]+Size[i],Length)-Bucket[0][i];
if(Bucket[0][i][Key]==Length)
Key++;
if(Key<Size[i]) {
Ans+=Cnt[i][Key];
Length=Next[i][Key];
}
}
return Ans;
}
int update(int i, int y) {
Delete(i);
Insert(y,i);
Num++;
if(!(Num%BucketNum))
ReArrange();
return FindAns();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
24068 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
24068 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
20 ms |
24068 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
24 ms |
24064 KB |
SIGSEGV Segmentation fault |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
88 ms |
24064 KB |
SIGSEGV Segmentation fault |
2 |
Halted |
0 ms |
0 KB |
- |