oj.uz

Submission #13809

# Submission time Handle Problem Language Result Execution time Memory
13809 2015-04-02T01:40:59 Z gs14004 Dancing Elephants (IOI11_elephants) C++14
100 / 100
 5286 ms 21116 KB 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

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

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

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

elem bucket[305][905];
int size[305];

int sentinel;

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

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(){
    int piv = 0;
    for (int i=0; i<sentinel; i++) {
        for (int j=0; j<size[i]; j++) {
            b[piv++] = bucket[i][j].val;
        }
    }
    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();
}

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){
        bucket_clear();
    }
    return query();
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 21116 KB Output is correct
2 Correct 510 ms 21116 KB Output is correct
3 Correct 651 ms 21116 KB Output is correct
4 Correct 616 ms 21116 KB Output is correct
5 Correct 558 ms 21116 KB Output is correct
6 Correct 911 ms 21116 KB Output is correct
7 Correct 633 ms 21116 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 608 ms 21116 KB Output is correct
2 Correct 758 ms 21116 KB Output is correct
3 Correct 1509 ms 21116 KB Output is correct
4 Correct 1581 ms 21116 KB Output is correct
5 Correct 1667 ms 21116 KB Output is correct
6 Correct 1057 ms 21116 KB Output is correct
7 Correct 1564 ms 21116 KB Output is correct
8 Correct 1489 ms 21116 KB Output is correct
9 Correct 1050 ms 21116 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4457 ms 21116 KB Output is correct
2 Correct 4635 ms 21116 KB Output is correct
3 Correct 3611 ms 21116 KB Output is correct
4 Correct 4009 ms 21116 KB Output is correct
5 Correct 4182 ms 21116 KB Output is correct
6 Correct 2276 ms 21116 KB Output is correct
7 Correct 2188 ms 21116 KB Output is correct
8 Correct 2272 ms 21116 KB Output is correct
9 Correct 2167 ms 21116 KB Output is correct
10 Correct 3482 ms 21116 KB Output is correct
11 Correct 2996 ms 21116 KB Output is correct
12 Correct 3629 ms 21116 KB Output is correct
13 Correct 3031 ms 21116 KB Output is correct
14 Correct 2531 ms 21116 KB Output is correct
15 Correct 4257 ms 21116 KB Output is correct
16 Correct 3690 ms 21116 KB Output is correct
17 Correct 3782 ms 21116 KB Output is correct
18 Correct 3742 ms 21116 KB Output is correct
19 Correct 5236 ms 21116 KB Output is correct
20 Correct 5286 ms 21116 KB Output is correct