#include <cstdio>
#include <algorithm>
using namespace std;
int N,M,L;
int B=500;
struct group{
int sz,p[810],cnt[810],nxt[810];
void init(){
int id=sz-1;
for(int i=sz-1;i>=0;i--){
if(p[sz-1]-p[i]<=L)cnt[i]=1,nxt[i]=p[i]+L+1;
else{
while(p[id]-p[i]>L)id--;
cnt[i]=cnt[id+1]+1;
nxt[i]=nxt[id+1];
}
}
}
void push(int x){
int id=0;
while(id<sz&&p[id]<=x)id++;
sz++;
for(int i=sz-1;i>id;i--)p[i]=p[i-1];
p[id]=x;
init();
}
void pop(int x){
int id=0;
while(p[id]<=x)id++;
for(int i=id;i<sz;i++)p[i-1]=p[i];
sz--;
init();
}
}a[500];
struct elephant{
int p,group_id,id;
bool operator<(const elephant& r)const{
return p<r.p;
}
}b[150010];
int ID[150010];
void renewal(){
sort(b,b+N);
for(int i=0;i<M;i++)a[i].sz=0;
for(int i=0;i<N;i++){
ID[b[i].id]=i;
b[i].group_id=i/B;
a[i/B].p[a[i/B].sz++]=b[i].p;
M=max(M,i/B+1);
}
for(int i=0;i<M;i++){
a[i].init();
}
}
void init(int N_, int L_, int X[]){
N=N_;
L=L_;
for(int i=0;i<N;i++)b[i]=elephant{X[i],i/B,i};
renewal();
}
int findGroup(int x){
if(a[0].p[0]>x)return 0;
for(int i=0;i<M-1;i++){
if(a[i].p[0]<=x&&x<a[i+1].p[0])return i;
}
return M-1;
}
int calc(){
int x=0,ret=0;
for(int i=0;i<M;i++){
int id=lower_bound(a[i].p,a[i].p+a[i].sz,x)-a[i].p;
if(id==a[i].sz)continue;
ret+=a[i].cnt[id];
x=a[i].nxt[id];
}
return ret;
}
int update(int i, int y){
int id=b[ID[i]].group_id;
a[id].pop(b[ID[i]].p);
b[ID[i]].p=y;
if(a[id].sz==0){
renewal();
return calc();
}
id=b[ID[i]].group_id=findGroup(y);
a[id].push(y);
if(a[id].sz>800)renewal();
return calc();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
23804 KB |
Output is correct |
2 |
Correct |
0 ms |
23804 KB |
Output is correct |
3 |
Correct |
0 ms |
23804 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
23804 KB |
Output is correct |
2 |
Correct |
0 ms |
23804 KB |
Output is correct |
3 |
Correct |
0 ms |
23804 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
368 ms |
23804 KB |
Output is correct |
2 |
Correct |
369 ms |
23804 KB |
Output is correct |
3 |
Correct |
440 ms |
23804 KB |
Output is correct |
4 |
Correct |
1473 ms |
23804 KB |
Output is correct |
5 |
Correct |
1425 ms |
23804 KB |
Output is correct |
6 |
Correct |
704 ms |
23804 KB |
Output is correct |
7 |
Correct |
1462 ms |
23804 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
564 ms |
23804 KB |
Output is correct |
2 |
Correct |
574 ms |
23804 KB |
Output is correct |
3 |
Correct |
1120 ms |
23804 KB |
Output is correct |
4 |
Correct |
1152 ms |
23804 KB |
Output is correct |
5 |
Correct |
1216 ms |
23804 KB |
Output is correct |
6 |
Correct |
2829 ms |
23804 KB |
Output is correct |
7 |
Correct |
1142 ms |
23804 KB |
Output is correct |
8 |
Correct |
1089 ms |
23804 KB |
Output is correct |
9 |
Correct |
2811 ms |
23804 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2466 ms |
23804 KB |
Output is correct |
2 |
Correct |
2632 ms |
23804 KB |
Output is correct |
3 |
Correct |
1990 ms |
23804 KB |
Output is correct |
4 |
Execution timed out |
9000 ms |
23800 KB |
Program timed out |
5 |
Halted |
0 ms |
0 KB |
- |