oj.uz

Submission #13804

# Submission time Handle Problem Language Result Execution time Memory
13804 2015-04-02T01:29:23 Z gs14004 Dancing Elephants (IOI11_elephants) C++14
100 / 100
 5350 ms 20884 KB 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

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

// O(NlgB) - U = B
struct elem{
    int val;
    int next;
    int cnt;
};

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

elem bucket[255][1005];
int size[255];

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

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 20884 KB Output is correct
2 Correct 538 ms 20884 KB Output is correct
3 Correct 654 ms 20884 KB Output is correct
4 Correct 513 ms 20884 KB Output is correct
5 Correct 524 ms 20884 KB Output is correct
6 Correct 985 ms 20884 KB Output is correct
7 Correct 531 ms 20884 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 20884 KB Output is correct
2 Correct 820 ms 20884 KB Output is correct
3 Correct 1669 ms 20884 KB Output is correct
4 Correct 1675 ms 20884 KB Output is correct
5 Correct 1788 ms 20884 KB Output is correct
6 Correct 992 ms 20884 KB Output is correct
7 Correct 1681 ms 20884 KB Output is correct
8 Correct 1582 ms 20884 KB Output is correct
9 Correct 960 ms 20884 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4278 ms 20884 KB Output is correct
2 Correct 4577 ms 20884 KB Output is correct
3 Correct 3385 ms 20884 KB Output is correct
4 Correct 3763 ms 20884 KB Output is correct
5 Correct 3904 ms 20884 KB Output is correct
6 Correct 2778 ms 20884 KB Output is correct
7 Correct 2703 ms 20884 KB Output is correct
8 Correct 2735 ms 20884 KB Output is correct
9 Correct 2701 ms 20884 KB Output is correct
10 Correct 4102 ms 20884 KB Output is correct
11 Correct 2880 ms 20884 KB Output is correct
12 Correct 3399 ms 20884 KB Output is correct
13 Correct 2859 ms 20884 KB Output is correct
14 Correct 2451 ms 20884 KB Output is correct
15 Correct 4121 ms 20884 KB Output is correct
16 Correct 3439 ms 20884 KB Output is correct
17 Correct 3459 ms 20884 KB Output is correct
18 Correct 3455 ms 20884 KB Output is correct
19 Correct 5267 ms 20884 KB Output is correct
20 Correct 5350 ms 20884 KB Output is correct