oj.uz

Submission #13800

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

const int U = 400;
const int B = 1500; // 400 ~ 1500

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

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

elem bucket[105][2000];
int size[105];

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1274 ms 20340 KB Output is correct
2 Correct 1291 ms 20340 KB Output is correct
3 Correct 1118 ms 20340 KB Output is correct
4 Correct 828 ms 20340 KB Output is correct
5 Correct 762 ms 20340 KB Output is correct
6 Correct 1852 ms 20340 KB Output is correct
7 Correct 841 ms 20340 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1440 ms 20340 KB Output is correct
2 Correct 1880 ms 20340 KB Output is correct
3 Correct 3238 ms 20340 KB Output is correct
4 Correct 2971 ms 20340 KB Output is correct
5 Correct 3251 ms 20340 KB Output is correct
6 Correct 1448 ms 20340 KB Output is correct
7 Correct 2968 ms 20340 KB Output is correct
8 Correct 2789 ms 20340 KB Output is correct
9 Correct 1443 ms 20340 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5466 ms 20340 KB Output is correct
2 Correct 6181 ms 20340 KB Output is correct
3 Correct 4149 ms 20340 KB Output is correct
4 Correct 5355 ms 20340 KB Output is correct
5 Correct 5389 ms 20340 KB Output is correct
6 Correct 6547 ms 20340 KB Output is correct
7 Correct 6422 ms 20340 KB Output is correct
8 Correct 6549 ms 20340 KB Output is correct
9 Correct 6426 ms 20340 KB Output is correct
10 Correct 4168 ms 20340 KB Output is correct
11 Correct 3450 ms 20340 KB Output is correct
12 Correct 4116 ms 20340 KB Output is correct
13 Correct 3702 ms 20340 KB Output is correct
14 Correct 3047 ms 20340 KB Output is correct
15 Correct 5237 ms 20340 KB Output is correct
16 Correct 4178 ms 20340 KB Output is correct
17 Correct 4123 ms 20340 KB Output is correct
18 Correct 4191 ms 20340 KB Output is correct
19 Correct 7536 ms 20340 KB Output is correct
20 Correct 7715 ms 20340 KB Output is correct