제출 #124104

#제출 시각아이디문제언어결과실행 시간메모리
124104nxteru코끼리 (Dancing Elephants) (IOI11_elephants)C++14
100 / 100
3250 ms12564 KiB
#include "elephants.h" #include <bits/stdc++.h> using namespace std; #define MAX_N 150005 #define B 400 int n,k,bs[MAX_N/B+2],p[MAX_N],pl[MAX_N],l,cnt,ds[MAX_N/B+2][B*2+1],sz[MAX_N/B+2][B*2+1],el[MAX_N/B+2][B*2+1]; void Bini(int x,int *xel,int xbs,int *xds,int *xsz){ int r=xbs; for(int i=xbs-1;i>=0;i--){ while(r-1>=0&&xel[i]+l<xel[r-1])r--; if(r==xbs){ xds[i]=xel[i]+l; xsz[i]=1; }else{ xds[i]=xds[r]; xsz[i]=xsz[r]+1; } } } void ALLini(bool start){ if(start)for(int i=0;i<n;i++)pl[i]=p[i]; else{ int sx=0; for(int i=0;i<=k;i++)for(int j=0;j<bs[i];j++)pl[sx++]=el[i][j]; } bs[0]=0; k=0; for(int i=0;i<n;i++){ if(bs[k]>=B){ k++; bs[k]=0; } el[k][bs[k]]=pl[i]; bs[k]++; } for(int i=0;i<=k;i++)Bini(i,el[i],bs[i],ds[i],sz[i]); } void init(int N, int L, int X[]){ n=N,l=L; for(int i=0;i<n;i++)p[i]=X[i]; ALLini(1); } int update(int t, int y){ int a=-1,b=p[t]; while(a+1<=k&&bs[a+1]==0||(bs[a+1]>=1&&el[a+1][0]<=b))a++; if(a==-1)a=0; bool sw=false; for(int i=0;i<bs[a]-1;i++){ if(el[a][i]==b)sw=true; if(sw)el[a][i]=el[a][i+1]; } bs[a]--; Bini(a,el[a],bs[a],ds[a],sz[a]); p[t]=y; a=-1; while(a+1<=k&&bs[a+1]==0||(bs[a+1]>=1&&el[a+1][0]<=y))a++; if(a==-1)a=0; el[a][bs[a]]=y; bs[a]++; for(int i=bs[a]-1;i>0;i--)if(el[a][i]<el[a][i-1])swap(el[a][i],el[a][i-1]); Bini(a,el[a],bs[a],ds[a],sz[a]); int ans=0; a=0,b=-1; for(;a<=k;a++){ if(bs[a]==0)continue; int c=upper_bound(el[a],el[a]+bs[a],b)-el[a]; if(c==bs[a])continue; ans+=sz[a][c]; b=ds[a][c]; } cnt++; if(cnt>=B){ cnt=0; ALLini(0); } return ans; }

컴파일 시 표준 에러 (stderr) 메시지

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:45:14: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  while(a+1<=k&&bs[a+1]==0||(bs[a+1]>=1&&el[a+1][0]<=b))a++;
        ~~~~~~^~~~~~~~~~~~
elephants.cpp:56:14: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  while(a+1<=k&&bs[a+1]==0||(bs[a+1]>=1&&el[a+1][0]<=y))a++;
        ~~~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...