#include <cstdio>
#include <algorithm>
using namespace std;
int N,M,L;
int B=4;
struct group{
int sz,p[710],cnt[710],nxt[710];
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(p[id]<=x&&id<sz)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;
a[i/B].p[a[i/B].sz++]=b[i].p;
b[i].group_id=i/B;
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;i++)
if(a[i].p[0]<=x&&a[i].p[a[i].sz-1]>=x)
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;
int new_id=b[ID[i]].group_id=findGroup(y);
a[new_id].push(b[ID[i]].p);
if(a[id].sz==0||a[id].sz>700)renewal();
if(a[new_id].sz==0||a[new_id].sz>700)renewal();
return calc();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
23216 KB |
Output is correct |
2 |
Correct |
0 ms |
23216 KB |
Output is correct |
3 |
Correct |
0 ms |
23216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
23216 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
19 ms |
23212 KB |
SIGSEGV Segmentation fault |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
26 ms |
23212 KB |
SIGSEGV Segmentation fault |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
124 ms |
23212 KB |
SIGSEGV Segmentation fault |
2 |
Halted |
0 ms |
0 KB |
- |