| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 322107 | sean9892 | Dancing Elephants (IOI11_elephants) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
const int sq=400;
int N,L,G;
int arr[160000];
int inp[160000];
int con;
struct Bucket{
int brr[sq*2],cnt[sq*2],lst[sq*2];
int sz;
void f(){
int k=sz;
for(int i=sz;i>0;i--){
while(i<k&&brr[i]+L<brr[k-1])k--;
if(brr[i]+L>=brr[sz]){
cnt[i]=1;
lst[i]=brr[i]+L;
}
else{
cnt[i]=cnt[k]+1;
lst[i]=lst[k];
}
}
}
};
Bucket gr[sq];
void rel(){
con=0;
int idx=0;
for(int i=1;i<=G;i++){
for(int j=1;j<=gr[i].sz;j++){
idx++;
arr[idx]=gr[i].brr[j];
}
gr[i].sz=0;
}
G=1;
for(int i=1;i<=idx;i++){
if(gr[G].sz==sq-10)G++;
gr[G].sz++;
gr[G].brr[gr[G].sz]=arr[i];
}
for(int i=1;i<=G;i++){
gr[i].f();
}
}
void ins(int now){
int gi,id;
for(gi=1;gi<G;gi++){
if(now<gr[gi].brr[gr[gi].sz])break;
}
for(id=1;id<=gr[gi].sz;id++){
if(now<gr[gi].brr[id])break;
}
for(int i=gr[gi].sz;i>=id;i--){
gr[gi].brr[i+1]=gr[gi].brr[i];
}
gr[gi].sz++;
gr[gi].brr[id]=now;
gr[gi].f();
}
int del(int now){
int gi;
for(gi=1;gi<G;gi++){
if(gr[gi].brr[1]<=now&&gr[gi+1].brr[1]>now)break;
}
for(int i=1;i<=gr[gi].sz;i++){
if(gr[gi].brr[i]==now){
for(;i<gr[gi].sz;i++){
gr[gi].brr[i]=gr[gi].brr[i+1];
}
gr[gi].sz--;
break;
}
}
gr[gi].f();
return gr[gi].sz;
}
int query(){
int res=gr[1].cnt[1];
int lst=gr[1].lst[1];
for(int i=2;i<=G;i++){
if(!gr[i].sz||gr[i].brr[gr[i].sz]<=lst)continue;
int l=1,r=gr[i].sz;
int now;
while(l<=r){
int m=l+r>>1;
if(gr[i].brr[m]>lst){
now=m;
r=m-1;
}
else{
l=m+1;
}
res+=gr[i].cnt[now];
lst=gr[i].lst[now];
}
}
return res;
}
int update(int i,int y){
con++;
if(con==sq-10)rel();
if(!del(inp[i]))rel();
inp[i]=y;
ins(y);
return query();
}
void init(int n,int l,int x[])
N=n;L=l;G=1;
for(int i=0;i<N;i++){
inp[i]=x[i];
if(gr[G].sz==sq-10)G++;
gr[G].sz++;
gr[G].brr[gr[G].sz]=inp[i];
}
for(int i=1;i<=G;i++){
gr[i].f();
}
}