| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 7570 | dohyun0324 | Dancing Elephants (IOI11_elephants) | C11 | 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.
#include "elephants.h"
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
int ix,iy,n,l,m,r,p=1,q,k,a[150010],d[150010],dap,leng[150010],a2[150010];
struct data
{
int c,x,y,len,val;
}ar[400][800];
void balance(int sx,int sy,int slen)
{
if(ar[sx][sy].c>slen){
while(ar[sx][sy].c>slen){
sy--;
if(sy==0){sx--; sy=leng[sx];}
if(ar[sx][sy].c==0){ sx--; sy=leng[sx];}
}
sy++;
if(sy==leng[sx]+1) sx++, sy=1;
}
else{
while(ar[sx][sy].c<=slen){
if(ar[sx][sy].c==0) sx++, sy=1;
else{
sy++;
if(sy==leng[sx]+1) sx++, sy=1;
}
}
}
ix=sx; iy=sy;
}
void erase1(int x)
{
int i,j,*e,pos,b,kx,ky;
e=upper_bound(d+1,d+p+1,x);
pos=e-d-1;
while(!leng[pos]) pos--;
for(i=1;i<=leng[pos];i++){
if(ar[pos][i].c==x) break;
}
b=i;
for(i=b;i<=leng[pos];i++){
ar[pos][i].c=ar[pos][i+1].c; ar[pos][i].x=ar[pos][i+1].x; ar[pos][i].y=ar[pos][i+1].y; ar[pos][i].len=ar[pos][i+1].len; ar[pos][i].val=ar[pos][i+1].val;
}
if(b==1){
d[pos]=ar[pos][1].c;
}
leng[pos]--;
if(b==1) return;
kx=ar[pos][b-1].x; ky=ar[pos][b-1].y;
if(ky>leng[kx]) ky=leng[kx];
if(ky==0){kx--; ky=leng[kx];}
balance(kx,ky,ar[pos][b-1].len);
kx=ix; ky=iy;
for(i=b-1;i>=1;i--){
kx=ix; ky=iy;
while(ar[kx][ky].c-ar[pos][i].c>l){
ky--;
if(ky==0){kx--; ky=leng[kx];}
if(ar[kx][ky].c==0){ kx--; ky=leng[kx];}
}
ky++;
if(ky==leng[kx]+1){kx++; ky=1;}
if(kx==p+1){
ar[pos][i].val=0;
continue;
}
if(kx>pos){
ar[pos][i].x=kx;
ar[pos][i].y=ky;
ar[pos][i].len=ar[pos][i].c+l;
ar[pos][i].val=0;
continue;
}
ar[pos][i].x=ar[kx][ky].x;
ar[pos][i].y=ar[kx][ky].y;
ar[pos][i].len=ar[kx][ky].len;
ar[pos][i].val=ar[kx][ky].val+1;
}
}
void insert1(int x)
{
int i,j,*e,pos,b,kx,ky,sx,sy,slen;
e=upper_bound(d+1,d+p+1,x);
pos=e-d-1;
if(pos==0) pos=1, d[1]=x;
for(i=1;i<=leng[pos];i++){
if(ar[pos][i].c>x || ar[pos][i].x==0) break;
}
b=i;
sx=ar[pos][b].x; sy=ar[pos][b].y; slen=ar[pos][b].len;
for(i=leng[pos]+1;i>=b+1;i--){
ar[pos][i].c=ar[pos][i-1].c; ar[pos][i].x=ar[pos][i-1].x; ar[pos][i].y=ar[pos][i-1].y; ar[pos][i].len=ar[pos][i-1].len; ar[pos][i].val=ar[pos][i-1].val;
}
ar[pos][b].c=x;
if(b==1) d[pos]=ar[pos][b].c;
leng[pos]++;
if(b==leng[pos]) sx=pos+1, sy=1, slen=ar[pos][b].c+l;
balance(sx,sy,slen);
kx=ix; ky=iy;
for(i=b;i>=1;i--){
while(ar[kx][ky].c-ar[pos][i].c>l){
ky--;
if(ky==0){kx--; ky=leng[kx];}
if(ar[kx][ky].c==0){ kx--; ky=leng[kx];}
}
ky++;
if(ky==leng[kx]+1){kx++; ky=1;}
if(kx==p+1){
ar[pos][i].x=kx;
ar[pos][i].y=1;
ar[pos][i].len=ar[pos][i].c+l;
ar[pos][i].val=0;
continue;
}
if(kx>pos){
ar[pos][i].x=kx;
ar[pos][i].y=ky;
ar[pos][i].len=ar[pos][i].c+l;
ar[pos][i].val=0;
continue;
}
ar[pos][i].x=ar[kx][ky].x;
ar[pos][i].y=ar[kx][ky].y;
ar[pos][i].len=ar[kx][ky].len;
ar[pos][i].val=ar[kx][ky].val+1;
}
}
void query()
{
int kx,ky,i,j,sx,sy,slen;
for(i=1;;i++){
if(leng[i]!=0) break;
}
kx=i; ky=1;
while(1){
if(kx==p-1) kx=p-1;
sx=ar[kx][ky].x; sy=ar[kx][ky].y; slen=ar[kx][ky].len; dap+=ar[kx][ky].val+1;
if(sy>leng[sx]) sy=leng[sx];
if(sy==0){sx--; sy=leng[sx];}
balance(sx,sy,slen);
kx=ix; ky=iy;
if(kx==p+1) break;
}
}
void reset()
{
int i,j,kx,ky;
r=1;
for(i=1;i<=n;i++){
for(j=r;j<=n;j++){
if(a[j]-a[i]>l) break;
}
r=j;
if(q==k) p++, q=0;
q++;
if(r==n+1){
ar[p][q].x=n/k+1;
if(n%k!=0) ar[p][q].x++;
ar[p][q].y=1;
ar[p][q].c=a[i];
leng[p]++;
r--;
continue;
}
ar[p][q].x=(r-1)/k+1;
ar[p][q].y=r%k; if(ar[p][q].y==0) ar[p][q].y=k;
ar[p][q].c=a[i];
leng[p]++;
r--;
}
for(i=p;i>=1;i--){
for(j=leng[i];j>=1;j--){
if(i==ar[i][j].x){
kx=ar[i][j].x; ky=ar[i][j].y;
if(ar[kx][ky].x==0){ar[i][j].len=ar[i][j].c+l; continue;}
ar[i][j].x=ar[kx][ky].x; ar[i][j].y=ar[kx][ky].y; ar[i][j].val=ar[kx][ky].val+1; ar[i][j].len=ar[kx][ky].len;
}
else{
ar[i][j].len=ar[i][j].c+l;
}
}
d[i]=ar[i][1].c;
}
ar[p+1][1].c=2147483647;
}
void init(int N, int L, int X[])
{
int i,j,kx=1,ky=0,w;
n = N;
l=L;
for(i=1; i<=N; i++)
{
a[i]=X[i-1];
a[i]++;
a2[i]=a[i];
}
k=sqrt(n);
if(k*k<n) k++;
reset();
}
int update(int s, int t)
{
int i=0,j,kx=1,ky=0,w;
s++;
t++; i++;
erase1(a2[s]);
insert1(t);
dap=0;
query();
a2[s]=t;
if(i%k==0)
{
kx=1, ky=0, w=0;
while(1)
{
while(ky==leng[kx]) kx++, ky=0;
ky++;
if(kx>=p+1) break;
a[++w]=ar[kx][ky].c;
}
memset(leng,0,sizeof leng);
memset(ar,0,sizeof ar);
p=1, q=0;
reset();
}
return dap;
}