Submission #17982

#TimeUsernameProblemLanguageResultExecution timeMemory
17982suhgyuho_williamDancing Elephants (IOI11_elephants)C++98
100 / 100
3775 ms23740 KiB
#include <stdio.h> #include "elephants.h" #define Size 390 int n,L; int bucket[500][1000]; int last[500][1000],picture[500][1000]; int cnt[500]; int a[150002]; void setting(int x){ int i,t; if(cnt[x] == 0) return; last[x][cnt[x]-1] = bucket[x][cnt[x]-1]+L; picture[x][cnt[x]-1] = 1; t = cnt[x]-1; for(i=cnt[x]-2; i>=0; i--){ while(true){ if(bucket[x][t-1]-bucket[x][i] > L) t--; else break; } if(bucket[x][cnt[x]-1]-bucket[x][i] <= L){ last[x][i] = bucket[x][i]+L; picture[x][i] = 1; }else{ last[x][i] = last[x][t]; picture[x][i] = picture[x][t]+1; } } } int w,t; void del(int x){ int i; for(i=0; ; i++){ if(cnt[i] > 0 && bucket[i][cnt[i]-1] >= x) break; } w = i; for(i=0; i<cnt[w]; i++){ if(x == bucket[w][i]) break; } t = i; for(i=t+1; i<cnt[w]; i++){ bucket[w][i-1] = bucket[w][i]; } cnt[w]--; setting(w); } void add(int x){ int i,sum; sum = 0; for(i=0; ; i++){ if(cnt[i] > 0 && bucket[i][cnt[i]-1] > x) break; sum += cnt[i]; if(sum == n-1) break; } w = i; if(sum == n-1){ bucket[w][cnt[w]] = x; }else{ for(i=0; i<cnt[w]; i++){ if(bucket[w][i] > x) break; } t = i; for(i=cnt[w]; i>t; i--) bucket[w][i] = bucket[w][i-1]; bucket[w][t] = x; } cnt[w]++; setting(w); } int tmp[150002]; void Bucketset(){ int i,j; int sum,rear; sum = 0; rear = -1; for(i=0; ; i++){ if(cnt[i] == 0) continue; sum += cnt[i]; for(j=0; j<cnt[i]; j++) tmp[++rear] = bucket[i][j]; cnt[i] = 0; if(sum == n) break; } for(i=0; i<=rear; i++){ bucket[i/Size][i%Size] = tmp[i]; cnt[i/Size]++; } for(i=0; i<=(rear/Size); i++) setting(i); } void mmain(void){ int i,j,k,m; int x,y,sum; int ans,e; int left,mid,right; //freopen("input.txt","r",stdin); for(i=0; i<n; i++){ bucket[i/Size][i%Size] = a[i]; cnt[i/Size]++; } for(i=0; i<=(n-1)/Size; i++){ setting(i); } } int ccnt = 0; int update(int x,int y){ int j,k,m; int sum; int ans,e; int left,mid,right; del(a[x]); ccnt++; add(y); a[x] = y; sum = 0; ans = 0; e = -1; for(j=0; ; j++){ if(sum == n) break; if(cnt[j] == 0) continue; sum += cnt[j]; if(e < bucket[j][0]){ e = last[j][0]; ans += picture[j][0]; }else if(bucket[j][cnt[j]-1] > e){ left = 0; right = cnt[j]-1; while(true){ mid = (left+right)/2; if(bucket[j][mid] <= e && bucket[j][mid+1] > e) break; if(bucket[j][mid] > e) right = mid-1; else left = mid+1; } e = last[j][mid+1]; ans += picture[j][mid+1]; } } if(ccnt%Size == 0) Bucketset(); return ans; } void init(int N, int ll, int X[]) { int i; n = N; L = ll; for(i=0; i<n; i++) a[i] = X[i]; mmain(); }
#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...