oj.uz

Submission #5065

# Submission time Handle Problem Language Result Execution time Memory
5065 2014-01-31T05:55:53 Z tncks0121 Dancing Elephants (IOI11_elephants) C++
100 / 100
 6156 ms 23284 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 23284 KB Output is correct
2 Correct 0 ms 23284 KB Output is correct
3 Correct 0 ms 23284 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 23284 KB Output is correct
2 Correct 0 ms 23284 KB Output is correct
3 Correct 0 ms 23284 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 23284 KB Output is correct
2 Correct 340 ms 23284 KB Output is correct
3 Correct 532 ms 23284 KB Output is correct
4 Correct 472 ms 23284 KB Output is correct
5 Correct 480 ms 23284 KB Output is correct
6 Correct 736 ms 23284 KB Output is correct
7 Correct 476 ms 23284 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 23284 KB Output is correct
2 Correct 576 ms 23284 KB Output is correct
3 Correct 1208 ms 23284 KB Output is correct
4 Correct 1588 ms 23284 KB Output is correct
5 Correct 1624 ms 23284 KB Output is correct
6 Correct 1200 ms 23284 KB Output is correct
7 Correct 1620 ms 23284 KB Output is correct
8 Correct 1580 ms 23284 KB Output is correct
9 Correct 992 ms 23284 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4956 ms 23284 KB Output is correct
2 Correct 5112 ms 23284 KB Output is correct
3 Correct 4172 ms 23284 KB Output is correct
4 Correct 4728 ms 23284 KB Output is correct
5 Correct 4700 ms 23284 KB Output is correct
6 Correct 636 ms 23284 KB Output is correct
7 Correct 592 ms 23284 KB Output is correct
8 Correct 624 ms 23284 KB Output is correct
9 Correct 564 ms 23284 KB Output is correct
10 Correct 4684 ms 23284 KB Output is correct
11 Correct 3240 ms 23284 KB Output is correct
12 Correct 4232 ms 23284 KB Output is correct
13 Correct 3400 ms 23284 KB Output is correct
14 Correct 3108 ms 23284 KB Output is correct
15 Correct 5328 ms 23284 KB Output is correct
16 Correct 4128 ms 23284 KB Output is correct
17 Correct 3940 ms 23284 KB Output is correct
18 Correct 3952 ms 23284 KB Output is correct
19 Correct 5976 ms 23284 KB Output is correct
20 Correct 6156 ms 23284 KB Output is correct