oj.uz

Submission #17557

# Submission time Handle Problem Language Result Execution time Memory
17557 2015-12-27T08:05:53 Z tncks0121 Dancing Elephants (IOI11_elephants) C++14
100 / 100
 4355 ms 23292 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 23292 KB Output is correct
2 Correct 0 ms 23292 KB Output is correct
3 Correct 0 ms 23292 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 23292 KB Output is correct
2 Correct 346 ms 23292 KB Output is correct
3 Correct 450 ms 23292 KB Output is correct
4 Correct 411 ms 23292 KB Output is correct
5 Correct 463 ms 23292 KB Output is correct
6 Correct 698 ms 23292 KB Output is correct
7 Correct 425 ms 23292 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 23292 KB Output is correct
2 Correct 555 ms 23292 KB Output is correct
3 Correct 1096 ms 23292 KB Output is correct
4 Correct 1298 ms 23292 KB Output is correct
5 Correct 1321 ms 23292 KB Output is correct
6 Correct 761 ms 23292 KB Output is correct
7 Correct 1268 ms 23292 KB Output is correct
8 Correct 1218 ms 23292 KB Output is correct
9 Correct 729 ms 23292 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3383 ms 23292 KB Output is correct
2 Correct 3494 ms 23292 KB Output is correct
3 Correct 2685 ms 23292 KB Output is correct
4 Correct 3051 ms 23292 KB Output is correct
5 Correct 3021 ms 23292 KB Output is correct
6 Correct 585 ms 23292 KB Output is correct
7 Correct 533 ms 23292 KB Output is correct
8 Correct 575 ms 23292 KB Output is correct
9 Correct 534 ms 23292 KB Output is correct
10 Correct 2906 ms 23292 KB Output is correct
11 Correct 2382 ms 23292 KB Output is correct
12 Correct 2570 ms 23292 KB Output is correct
13 Correct 2546 ms 23292 KB Output is correct
14 Correct 2772 ms 23292 KB Output is correct
15 Correct 3476 ms 23292 KB Output is correct
16 Correct 2622 ms 23292 KB Output is correct
17 Correct 2520 ms 23292 KB Output is correct
18 Correct 2600 ms 23292 KB Output is correct
19 Correct 4329 ms 23292 KB Output is correct
20 Correct 4355 ms 23292 KB Output is correct