oj.uz

답안 #13807

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13807 2015-04-02T01:35:01 Z gs14004 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
100 / 100
 5441 ms 21700 KB 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int U = 400;
const int B = 400;

struct elem{
    int val;
    int next;
    int cnt;
};

bool operator<(elem a, elem b){ return a.val < b.val; }

elem bucket[405][805];
int size[405];

int sentinel;

int b[150005];
int a[150005], n, l;
int q_cnt;

void make_arr(){
    int piv = 0;
    for (int i=0; i<sentinel; i++) {
        for (int j=0; j<size[i]; j++) {
            b[piv++] = bucket[i][j].val;
        }
    }
}

void bucket_label(int bnum){
    int pt = size[bnum];
    for (int i=size[bnum]-1; i>=0; i--) {
        while (pt && bucket[bnum][pt-1].val > bucket[bnum][i].val + l) {
            pt--;
        }
        if(pt == size[bnum]){
            bucket[bnum][i].next = -1;
            bucket[bnum][i].cnt = 0;
        }
        else{
            if(bucket[bnum][pt].next == -1){
                bucket[bnum][i].next = pt;
            }
            else{
                bucket[bnum][i].next = bucket[bnum][pt].next;
            }
            bucket[bnum][i].cnt = bucket[bnum][pt].cnt + 1;
        }
    }
}

void bucket_clear(){
    for (int i=0; i<sentinel; i++) {
        size[i] = min(n-i*B,B);
        for (int j=0; j<size[i]; j++) {
            bucket[i][j].val = b[i*B + j];
        }
        bucket_label(i);
    }
}

void bucket_erase(int bnum, int pos){
    size[bnum]--;
    for (int i=pos; i<size[bnum]; i++) {
        bucket[bnum][i] = bucket[bnum][i+1];
    }
    bucket_label(bnum);
}

void bucket_update(int bnum, int pos, int val){
    size[bnum]++;
    for (int i=size[bnum]-1; i>pos; i--) {
        bucket[bnum][i] = bucket[bnum][i-1];
    }
    bucket[bnum][pos].val = val;
    bucket_label(bnum);
}

int query(){
    int pos = 0, ret = 0;
    for (int i=0; i<sentinel; ) {
        if(!size[i]){
            i++;
            continue;
        }
        
        ret += bucket[i][pos].cnt + 1;
        if(bucket[i][pos].next != -1) pos = bucket[i][pos].next;
        
        int new_buck = i+1;
        int new_pos = bucket[i][pos].val + l;
        while (1){
            if(new_buck == sentinel) break;
            if(lower_bound(bucket[new_buck],bucket[new_buck] + size[new_buck],(elem){new_pos+1,0,0})
               != bucket[new_buck] + size[new_buck]) break;
            new_buck++;
        }
        
        if(new_buck == sentinel) break;
        i = new_buck;
        
        pos = (int)(lower_bound(bucket[new_buck],bucket[new_buck] + size[new_buck],(elem){new_pos+1,0,0}) - bucket[new_buck]);
    }
    return ret;
}

void init(int N, int L, int* X){
    memcpy(a,X,sizeof(int) * N);
    memcpy(b,a,sizeof(int) * N);
    n = N;
    l = L;
    while (sentinel * B < n) sentinel++;
    bucket_clear();
}

// O(N/(B+U)lgB + B)
int update(int i, int y){
    q_cnt = (q_cnt + 1) % U;
    int o = a[i];
    a[i] = y;
    for (int i=0; i<sentinel; i++) {
        if(!size[i]) continue;
        else if(bucket[i][0].val <= o && o <= bucket[i][size[i]-1].val){
            int pos = (int)(lower_bound(bucket[i],bucket[i] + size[i],(elem){o,0,0}) - bucket[i]);
            bucket_erase(i,pos);
            break;
        }
    }
    int low = -1;
    for (int i=0; i<sentinel; i++) {
        if(!size[i]) continue;
        if(bucket[i][0].val <= y) low = i;
    }
    if(low == -1){
        bucket_update(0,0,y);
    }
    else{
        int pos = (int)(lower_bound(bucket[low],bucket[low] + size[low],(elem){y,0,0}) - bucket[low]);
        bucket_update(low,pos,y);
    }
    if(q_cnt == 0){
        make_arr();
        bucket_clear();
    }
    return query();
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 21700 KB Output is correct
2 Correct 0 ms 21700 KB Output is correct
3 Correct 0 ms 21700 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 21700 KB Output is correct
2 Correct 0 ms 21700 KB Output is correct
3 Correct 0 ms 21700 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 404 ms 21700 KB Output is correct
2 Correct 431 ms 21700 KB Output is correct
3 Correct 593 ms 21700 KB Output is correct
4 Correct 569 ms 21700 KB Output is correct
5 Correct 555 ms 21700 KB Output is correct
6 Correct 846 ms 21700 KB Output is correct
7 Correct 595 ms 21700 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 511 ms 21700 KB Output is correct
2 Correct 687 ms 21700 KB Output is correct
3 Correct 1399 ms 21700 KB Output is correct
4 Correct 1502 ms 21700 KB Output is correct
5 Correct 1581 ms 21700 KB Output is correct
6 Correct 1050 ms 21700 KB Output is correct
7 Correct 1509 ms 21700 KB Output is correct
8 Correct 1425 ms 21700 KB Output is correct
9 Correct 1035 ms 21700 KB Output is correct

Subtask #5
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4673 ms 21700 KB Output is correct
2 Correct 4839 ms 21700 KB Output is correct
3 Correct 3747 ms 21700 KB Output is correct
4 Correct 4227 ms 21700 KB Output is correct
5 Correct 4359 ms 21700 KB Output is correct
6 Correct 1871 ms 21700 KB Output is correct
7 Correct 1779 ms 21700 KB Output is correct
8 Correct 1850 ms 21700 KB Output is correct
9 Correct 1774 ms 21700 KB Output is correct
10 Correct 3953 ms 21700 KB Output is correct
11 Correct 3081 ms 21700 KB Output is correct
12 Correct 3777 ms 21700 KB Output is correct
13 Correct 3086 ms 21700 KB Output is correct
14 Correct 2612 ms 21700 KB Output is correct
15 Correct 4450 ms 21700 KB Output is correct
16 Correct 3854 ms 21700 KB Output is correct
17 Correct 3908 ms 21700 KB Output is correct
18 Correct 3983 ms 21700 KB Output is correct
19 Correct 5331 ms 21700 KB Output is correct
20 Correct 5441 ms 21700 KB Output is correct