Submission #5065

#	Time	Username	Problem	Language	Result	Execution time	Memory
5065		tncks0121	Dancing Elephants (IOI11_elephants)	C++98	100 / 100	6156 ms	23284 KiB

elephants

#include<stdio.h>
#include<math.h>
 
int N, L, Q;
 
#define bN 390
#define N_ 150000
 
int tmp[N_+1], tmp2[N_+1];
 
class Elephant {
    int bucket [bN+1][2*bN+5];
    int cnt [bN+1];
    int cameras [bN+1][2*bN+5];
    int end [bN+1][2*bN+5];
    int number [bN+1][2*bN+5];
    int wh [N_+1];
 
    int bn, bl;
    int jcnt;
 
    void solve(int num){ // bucket[num]에 대해 cameras, end 문제 해결
        int *b = bucket[num], *c = cameras[num], *e = end[num];
        int i, j = cnt[num] + 1; c[j] = 0;
        for(i = cnt[num]; i > 0; i--){
            while(b[--j] - b[i] > L); j++;
            c[i] = c[j] + 1; 
            if(j <= cnt[num]) e[i] = e[j];
            else e[i] = b[i] + L;
        }
    }
 
    void init(){
        int i, j, tn = 0;
        for(i=1; i<=bn; i++){
            for(j=1; j<=cnt[i]; j++){
                tmp[++tn] = bucket[i][j];
                tmp2[tn] = number[i][j];
            }
            cnt[i] = 0;
        }
        bn = 1;
        for(i=1; i<=N; i++){
            bucket[bn][++cnt[bn]] = tmp[i];
            number[bn][cnt[bn]] = tmp2[i];
            wh[tmp2[i]] = bn;
            if(cnt[bn] == bl) solve(bn++);
        }
        if(cnt[bn]) solve(bn); else bn--;
    }
 
    void find_by_num(int e,int &bx,int &by){
        bx = wh[e];
        for(by=1; by<=cnt[bx]; by++){
            if(number[bx][by] == e) break;
        }
    }
 
    void find_by_pos (int x,int &bx,int &by){
        for(bx=1; bx<=bn; bx++){
            if(bucket[bx][cnt[bx]] >= x) break;
        }
        if(bx > bn) bx = bn;
        for(by=1; by<=cnt[bx]; by++){ if(bucket[bx][by] >= x) break; } 
    }
 
    int solve_cameras (){
        int i, x = bucket[1][1] + L, ret = 1;
        for(i=1; i<=bn; i++){
            int left=1, right=cnt[i], last = -1;
            while(left <= right){
                int mid = (left+right)>>1;
                if(bucket[i][mid] > x){
                    last = mid; right = mid - 1;
                }else left = mid + 1;
            }
            if(last > 0){
                ret += cameras[i][last];
                x = end[i][last];
            }
        }
        return ret;
    }
public:
    void input(int *X){
        int i; bn = 1; bl = 1+(int)sqrt((double)N);
        for(i=1; i<=N; i++){
            bucket[bn][++cnt[bn]] = X[i-1];
            number[bn][cnt[bn]] = i; wh[i] = bn;
            if(cnt[bn] == bl) solve(bn++);
        }
        if(cnt[bn]) solve(bn); else bn--;
    }
 
    int jump(int e, int p){ //e번 코끼리가 p 위치로 jump
        int ex, ey, px, py, i;
 
        find_by_num(e, ex, ey);
        for(i=ey; i<cnt[ex]; i++){
            bucket[ex][i] = bucket[ex][i+1];
            number[ex][i] = number[ex][i+1];
        }
        cnt[ex]--; solve(ex);
 
        find_by_pos(p, px, py); ++cnt[px];
        for(i=cnt[px]; i>py; i--){
            bucket[px][i] = bucket[px][i-1];
            number[px][i] = number[px][i-1];
        }
        bucket[px][py] = p; number[px][py] = e; 
        wh[e] = px; solve(px);
 
        if(++jcnt == bl) init(), jcnt = 0;
 
        return solve_cameras();
    }
};
 
Elephant ele;
 
void init (int n, int l, int *X) {
 N = n; L = l;
    ele.input(X);
}

int update (int i, int y) {
 return ele.jump(i+1, y);
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3