#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];
if(!Size[X])
return;
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[]) {
int BucketNow=0;
N=N_;
L=L_;
BucketNum=BucketLimit=sqrt(N);
if(BucketNum*BucketNum!=N) {
BucketNum++;
BucketLimit++;
}
for(int i=0 ; i<N ; i++) {
Bucket[0][BucketNow][Size[BucketNow]]=X[i];
Bucket[1][BucketNow][Size[BucketNow]]=i;
Loc[i][0]=BucketNow;
Loc[i][1]=Size[BucketNow];
Size[BucketNow]++;
if(Size[BucketNow]==BucketLimit)
BucketNow++;
}
ReArrange();
}
void Delete(int Key) {
int X=Loc[Key][0], Y=Loc[Key][1];
for(int i=Y ; i<Size[X]-1 ; i++) {
Bucket[0][X][i]=Bucket[0][X][i+1];
Bucket[1][X][i]=Bucket[1][X][i+1];
Loc[Bucket[1][X][i]][0]=X;
Loc[Bucket[1][X][i]][1]=i;
}
Size[X]--;
GiveInfo(X);
}
void Insert(int X, int Y) {
int Key1, Key2;
for(Key1=0 ; Key1<BucketNum-1 ; Key1++)
if(Size[Key1] && X<=Bucket[0][Key1][Size[Key1]-1])
break;
for(Key2=0 ; Key2<Size[Key1] ; Key2++)
if(X<=Bucket[0][Key1][Key2])
break;
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[1][Key1][i]][0]=Key1;
Loc[Bucket[1][Key1][i]][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++)
if(Size[i]) {
Key=lower_bound(Bucket[0][i],Bucket[0][i]+Size[i],Length+1)-Bucket[0][i];
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 |
Correct |
0 ms |
24068 KB |
Output is correct |
2 |
Correct |
0 ms |
24068 KB |
Output is correct |
3 |
Correct |
0 ms |
24068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
24068 KB |
Output is correct |
2 |
Correct |
0 ms |
24068 KB |
Output is correct |
3 |
Correct |
0 ms |
24068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
296 ms |
24068 KB |
Output is correct |
2 |
Correct |
364 ms |
24068 KB |
Output is correct |
3 |
Correct |
584 ms |
24068 KB |
Output is correct |
4 |
Correct |
544 ms |
24068 KB |
Output is correct |
5 |
Correct |
552 ms |
24068 KB |
Output is correct |
6 |
Correct |
960 ms |
24068 KB |
Output is correct |
7 |
Correct |
548 ms |
24068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
488 ms |
24068 KB |
Output is correct |
2 |
Correct |
600 ms |
24068 KB |
Output is correct |
3 |
Correct |
1476 ms |
24068 KB |
Output is correct |
4 |
Correct |
1808 ms |
24068 KB |
Output is correct |
5 |
Correct |
1888 ms |
24068 KB |
Output is correct |
6 |
Correct |
1144 ms |
24068 KB |
Output is correct |
7 |
Correct |
1804 ms |
24068 KB |
Output is correct |
8 |
Correct |
1792 ms |
24068 KB |
Output is correct |
9 |
Correct |
1012 ms |
24068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4612 ms |
24068 KB |
Output is correct |
2 |
Correct |
4684 ms |
24068 KB |
Output is correct |
3 |
Correct |
3972 ms |
24068 KB |
Output is correct |
4 |
Correct |
4224 ms |
24068 KB |
Output is correct |
5 |
Correct |
4304 ms |
24068 KB |
Output is correct |
6 |
Correct |
624 ms |
24068 KB |
Output is correct |
7 |
Correct |
600 ms |
24068 KB |
Output is correct |
8 |
Correct |
648 ms |
24068 KB |
Output is correct |
9 |
Correct |
608 ms |
24068 KB |
Output is correct |
10 |
Correct |
4048 ms |
24068 KB |
Output is correct |
11 |
Correct |
3188 ms |
24068 KB |
Output is correct |
12 |
Correct |
3772 ms |
24068 KB |
Output is correct |
13 |
Correct |
3404 ms |
24068 KB |
Output is correct |
14 |
Correct |
4308 ms |
24068 KB |
Output is correct |
15 |
Correct |
5272 ms |
24068 KB |
Output is correct |
16 |
Correct |
3748 ms |
24068 KB |
Output is correct |
17 |
Correct |
4024 ms |
24068 KB |
Output is correct |
18 |
Correct |
3776 ms |
24068 KB |
Output is correct |
19 |
Correct |
6284 ms |
24068 KB |
Output is correct |
20 |
Correct |
6292 ms |
24068 KB |
Output is correct |