oj.uz

Submission #13801

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

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

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

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

elem bucket[155][1405];
int size[155];

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 800 ms 20432 KB Output is correct
2 Correct 824 ms 20432 KB Output is correct
3 Correct 830 ms 20432 KB Output is correct
4 Correct 811 ms 20432 KB Output is correct
5 Correct 718 ms 20432 KB Output is correct
6 Correct 1350 ms 20432 KB Output is correct
7 Correct 821 ms 20432 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 973 ms 20432 KB Output is correct
2 Correct 1216 ms 20432 KB Output is correct
3 Correct 2341 ms 20432 KB Output is correct
4 Correct 2227 ms 20432 KB Output is correct
5 Correct 2412 ms 20432 KB Output is correct
6 Correct 1266 ms 20432 KB Output is correct
7 Correct 2208 ms 20432 KB Output is correct
8 Correct 2074 ms 20432 KB Output is correct
9 Correct 1255 ms 20432 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4528 ms 20432 KB Output is correct
2 Correct 4937 ms 20432 KB Output is correct
3 Correct 3467 ms 20432 KB Output is correct
4 Correct 4073 ms 20432 KB Output is correct
5 Correct 4134 ms 20432 KB Output is correct
6 Correct 4393 ms 20432 KB Output is correct
7 Correct 4269 ms 20432 KB Output is correct
8 Correct 4387 ms 20432 KB Output is correct
9 Correct 4290 ms 20432 KB Output is correct
10 Correct 3222 ms 20432 KB Output is correct
11 Correct 2903 ms 20432 KB Output is correct
12 Correct 3450 ms 20432 KB Output is correct
13 Correct 3034 ms 20432 KB Output is correct
14 Correct 2545 ms 20432 KB Output is correct
15 Correct 4339 ms 20432 KB Output is correct
16 Correct 3515 ms 20432 KB Output is correct
17 Correct 3560 ms 20432 KB Output is correct
18 Correct 3582 ms 20432 KB Output is correct
19 Correct 5948 ms 20432 KB Output is correct
20 Correct 6128 ms 20432 KB Output is correct