oj.uz

Submission #13808

# Submission time Handle Problem Language Result Execution time Memory
13808 2015-04-02T01:40:23 Z gs14004 Dancing Elephants (IOI11_elephants) C++14
100 / 100
 5372 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 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();
}

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 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 448 ms 21116 KB Output is correct
2 Correct 473 ms 21116 KB Output is correct
3 Correct 606 ms 21116 KB Output is correct
4 Correct 597 ms 21116 KB Output is correct
5 Correct 540 ms 21116 KB Output is correct
6 Correct 904 ms 21116 KB Output is correct
7 Correct 627 ms 21116 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 583 ms 21116 KB Output is correct
2 Correct 731 ms 21116 KB Output is correct
3 Correct 1515 ms 21116 KB Output is correct
4 Correct 1564 ms 21116 KB Output is correct
5 Correct 1657 ms 21116 KB Output is correct
6 Correct 1028 ms 21116 KB Output is correct
7 Correct 1568 ms 21116 KB Output is correct
8 Correct 1474 ms 21116 KB Output is correct
9 Correct 1036 ms 21116 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4396 ms 21116 KB Output is correct
2 Correct 4631 ms 21116 KB Output is correct
3 Correct 3559 ms 21116 KB Output is correct
4 Correct 3972 ms 21116 KB Output is correct
5 Correct 4134 ms 21116 KB Output is correct
6 Correct 2283 ms 21116 KB Output is correct
7 Correct 2178 ms 21116 KB Output is correct
8 Correct 2293 ms 21116 KB Output is correct
9 Correct 2175 ms 21116 KB Output is correct
10 Correct 3463 ms 21116 KB Output is correct
11 Correct 2943 ms 21116 KB Output is correct
12 Correct 3543 ms 21116 KB Output is correct
13 Correct 3041 ms 21116 KB Output is correct
14 Correct 2542 ms 21116 KB Output is correct
15 Correct 4237 ms 21116 KB Output is correct
16 Correct 3669 ms 21116 KB Output is correct
17 Correct 3755 ms 21116 KB Output is correct
18 Correct 3763 ms 21116 KB Output is correct
19 Correct 5263 ms 21116 KB Output is correct
20 Correct 5372 ms 21116 KB Output is correct