oj.uz

Submission #13798

# Submission time Handle Problem Language Result Execution time Memory
13798 2015-04-02T00:48:44 Z gs14004 Dancing Elephants (IOI11_elephants) C++14
100 / 100
 8315 ms 22180 KB 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
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; }

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

void bucket_label(int bnum){
    int pt = (int)bucket[bnum].size();
    for (int i=(int)bucket[bnum].size()-1; i>=0; i--) {
        while (pt && bucket[bnum][pt-1].val > bucket[bnum][i].val + l) {
            pt--;
        }
        if(pt == bucket[bnum].size()){
            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++) {
        bucket[i].clear();
        int piv = min(n-i*B,B);
        bucket[i].resize(piv);
        for (int j=0; j<piv; j++) {
            bucket[i][j].val = b[i*B + j];
        }
        bucket_label(i);
    }
}

void bucket_erase(int bnum, int pos){
    for (int i=pos; i<bucket[bnum].size()-1; i++) {
        bucket[bnum][i] = bucket[bnum][i+1];
    }
    bucket[bnum].pop_back();
    bucket_label(bnum);
}

void bucket_update(int bnum, int pos, int val){
    bucket[bnum].push_back((elem){0,0,0});
    for (int i=(int)bucket[bnum].size()-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(bucket[i].empty()){
            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].begin(),bucket[new_buck].end(),(elem){new_pos+1,0,0})
              != bucket[new_buck].end()) break;
            new_buck++;
        }
        
        if(new_buck == sentinel) break;
        i = new_buck;
        
        pos = (int)(lower_bound(bucket[new_buck].begin(),bucket[new_buck].end(),(elem){new_pos+1,0,0}) - bucket[new_buck].begin());
    }
    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(bucket[i].empty()) continue;
        else if(bucket[i][0].val <= o && o <= bucket[i].back().val){
            int pos = (int)(lower_bound(bucket[i].begin(),bucket[i].end(),(elem){o,0,0}) - bucket[i].begin());
            bucket_erase(i,pos);
            break;
        }
    }
    int low = -1;
    for (int i=0; i<sentinel; i++) {
        if(bucket[i].empty()) 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].begin(),bucket[low].end(),(elem){y,0,0}) - bucket[low].begin());
        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 18380 KB Output is correct
2 Correct 0 ms 18380 KB Output is correct
3 Correct 0 ms 18380 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1167 ms 18668 KB Output is correct
2 Correct 1199 ms 18796 KB Output is correct
3 Correct 1111 ms 19248 KB Output is correct
4 Correct 804 ms 18944 KB Output is correct
5 Correct 701 ms 18944 KB Output is correct
6 Correct 1849 ms 19648 KB Output is correct
7 Correct 791 ms 18944 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1357 ms 18820 KB Output is correct
2 Correct 1753 ms 18936 KB Output is correct
3 Correct 3351 ms 19532 KB Output is correct
4 Correct 3116 ms 20080 KB Output is correct
5 Correct 3311 ms 20068 KB Output is correct
6 Correct 1426 ms 19236 KB Output is correct
7 Correct 3094 ms 20080 KB Output is correct
8 Correct 2841 ms 20068 KB Output is correct
9 Correct 1384 ms 19224 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5791 ms 21476 KB Output is correct
2 Correct 6305 ms 21336 KB Output is correct
3 Correct 4245 ms 21196 KB Output is correct
4 Correct 5007 ms 20068 KB Output is correct
5 Correct 5068 ms 20068 KB Output is correct
6 Correct 5697 ms 18528 KB Output is correct
7 Correct 5525 ms 18528 KB Output is correct
8 Correct 5718 ms 18528 KB Output is correct
9 Correct 5579 ms 18528 KB Output is correct
10 Correct 4082 ms 20068 KB Output is correct
11 Correct 3405 ms 20068 KB Output is correct
12 Correct 4052 ms 20068 KB Output is correct
13 Correct 3523 ms 20068 KB Output is correct
14 Correct 2904 ms 20068 KB Output is correct
15 Correct 5446 ms 21900 KB Output is correct
16 Correct 4079 ms 20068 KB Output is correct
17 Correct 4215 ms 20068 KB Output is correct
18 Correct 4080 ms 20068 KB Output is correct
19 Correct 8026 ms 22180 KB Output is correct
20 Correct 8315 ms 22040 KB Output is correct