oj.uz

Submission #13803

# Submission time Handle Problem Language Result Execution time Memory
13803 2015-04-02T01:24:30 Z gs14004 Dancing Elephants (IOI11_elephants) C++14
100 / 100
 5654 ms 20564 KB 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

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

// 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[190][1205];
int size[190];

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 20564 KB Output is correct
2 Correct 0 ms 20564 KB Output is correct
3 Correct 0 ms 20564 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 641 ms 20564 KB Output is correct
2 Correct 668 ms 20564 KB Output is correct
3 Correct 740 ms 20564 KB Output is correct
4 Correct 600 ms 20564 KB Output is correct
5 Correct 603 ms 20564 KB Output is correct
6 Correct 1158 ms 20564 KB Output is correct
7 Correct 621 ms 20564 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 818 ms 20564 KB Output is correct
2 Correct 993 ms 20564 KB Output is correct
3 Correct 1979 ms 20564 KB Output is correct
4 Correct 1914 ms 20564 KB Output is correct
5 Correct 2076 ms 20564 KB Output is correct
6 Correct 1011 ms 20564 KB Output is correct
7 Correct 1914 ms 20564 KB Output is correct
8 Correct 1817 ms 20564 KB Output is correct
9 Correct 984 ms 20564 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4296 ms 20564 KB Output is correct
2 Correct 4673 ms 20564 KB Output is correct
3 Correct 3382 ms 20564 KB Output is correct
4 Correct 3409 ms 20564 KB Output is correct
5 Correct 3552 ms 20564 KB Output is correct
6 Correct 3532 ms 20564 KB Output is correct
7 Correct 3449 ms 20564 KB Output is correct
8 Correct 3532 ms 20564 KB Output is correct
9 Correct 3436 ms 20564 KB Output is correct
10 Correct 3843 ms 20564 KB Output is correct
11 Correct 2481 ms 20564 KB Output is correct
12 Correct 2983 ms 20564 KB Output is correct
13 Correct 2610 ms 20564 KB Output is correct
14 Correct 2177 ms 20564 KB Output is correct
15 Correct 4137 ms 20564 KB Output is correct
16 Correct 3091 ms 20564 KB Output is correct
17 Correct 3070 ms 20564 KB Output is correct
18 Correct 3089 ms 20564 KB Output is correct
19 Correct 5492 ms 20564 KB Output is correct
20 Correct 5654 ms 20564 KB Output is correct