| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 262932 | dantoh000 | 코끼리 (Dancing Elephants) (IOI11_elephants) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define K 500
using namespace std;
#include "elephants.h"
int n, l, x[150005];
struct BUCKET{
int a[150005], ct[150005], r[150005], sz;
void comp(){
int k = sz-1;
for (int i = sz-1; i >= 0; i--){
while (k > i && a[k-1] - a[i] > l) k--;
if (a[sz-1] - a[i] <= l){
ct[i] = 1; r[i] = a[i]+L;
}
else ct[i] = ct[k]+1, r[i] = r[k];
//printf("%d -> %d: ct = %d, r = %d\n",a[i],a[k],ct[i],r[i]);
}
}
} bk[305];
void init(int N, int L, int X[])
{
n = N;
l = L;
for (int i = 0; i < n; i++) x[i] = X[i];
for (int i = 0; i <= n/K; i++){
bk[i].sz = 0;
for (int j = i*K; j < min((i+1)*K,n); j++){
bk[i].a[j%K] = x[j];
bk[i].sz++;
}
bk[i].comp();
}
}
void rebuild_all(){
int N = 0;
for (int i = 0; i <= n/K; i++){
for (int j = 0; j < bk[i].sz; j++){
x[N++] = bk[i].a[j];
}
}
for (int i = 0; i <= n/K; i++){
bk[i].sz = 0;
for (int j = i*K; j < min((i+1)*K,n); j++){
bk[i].a[j%K] = x[j];
bk[i].sz++;
}
bk[i].comp();
}
}
void add(int x){
//printf("adding %d\n",x);
for (int i = 0; i <= n/K; i++){
if (bk[i].sz == 0) continue;
if ((bk[i].a[0] <= x && x <= bk[i].a[bk[i].sz-1]) || i == (n-1)/K){
//printf("adding to bucket %d\n",i);
if (bk[i].a[0] > x){
//printf("position %d\n",0);
for (int k = bk[i].sz-1; k >= 0; k--){
bk[i].a[k+1] = bk[i].a[k];
}
bk[i].a[0] = x;
}
else{
for (int j = 0; j <= bk[i].sz; j++){
if ((bk[i].a[j] >= x && bk[i].a[j+1] < x) || j == bk[i].sz){
//printf("position %d\n",j);
for (int k = bk[i].sz-1; k >= j; k--){
bk[i].a[k+1] = bk[i].a[k];
}
bk[i].a[j] = x;
break;
}
}
}
bk[i].sz++;
bk[i].comp();
break;
}
}
}
void del(int x){
//printf("deleting %d\n",x);
for (int i = 0; i <= n/K; i++){
if (bk[i].sz == 0) continue;
if (bk[i].a[0] <= x && x <= bk[i].a[bk[i].sz-1]){
//printf("deleting from bucket %d\n",i);
for (int j = 0; j < bk[i].sz; j++){
if (bk[i].a[j] == x){
//printf("position %d\n",j);
for (int k = j; k < bk[i].sz; k++){
bk[i].a[k] = bk[i].a[k+1];
}
break;
}
}
bk[i].a[bk[i].sz] = 0;
bk[i].sz--;
bk[i].comp();
break;
}
}
}
int solve(){
//printf("solving\n");
int curpos = -1;
int ans = 0;
for (int i = 0; i <= n/K; i++){
if (bk[i].sz == 0) continue;
if (curpos == -1){
ans += bk[i].ct[0];
curpos = bk[i].r[0];
continue;
}
int nx = upper_bound(bk[i].a, bk[i].a+bk[i].sz,curpos+l) - bk[i].a;
ans += bk[i].ct[nx];
curpos = bk[i].r[nx];
}
return ans;
}
void debug(){
for (int i = 0; i <= n/K; i++){
printf("bucket %d: ",i);
for (int j = 0; j < bk[i].sz; j++){
printf("%d ",bk[i].a[j]);
}
printf("\n");
}
}
int numQ = 0;
int update(int i, int y)
{
if (++numQ == K){
rebuild_all();
numQ = 0;
}
del(x[i]);
x[i] = y;
add(x[i]);
//debug();
return solve();
}