oj.uz

Submission #13796

# Submission time Handle Problem Language Result Execution time Memory
13796 2015-04-02T00:39:23 Z gs14004 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 22176 KB 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int U = 100; // 400 ~ 1500
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;
        }
    }
    /****** insert y ******/
    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 1262 ms 18668 KB Output is correct
2 Correct 1321 ms 18796 KB Output is correct
3 Correct 1277 ms 19248 KB Output is correct
4 Correct 983 ms 18944 KB Output is correct
5 Correct 863 ms 18944 KB Output is correct
6 Correct 2162 ms 19648 KB Output is correct
7 Correct 977 ms 18944 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1459 ms 18820 KB Output is correct
2 Correct 1979 ms 18936 KB Output is correct
3 Correct 3824 ms 19532 KB Output is correct
4 Correct 3714 ms 20080 KB Output is correct
5 Correct 3974 ms 20068 KB Output is correct
6 Correct 1755 ms 19236 KB Output is correct
7 Correct 3721 ms 20104 KB Output is correct
8 Correct 3457 ms 20212 KB Output is correct
9 Correct 1719 ms 19224 KB Output is correct

Subtask #5
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7855 ms 21476 KB Output is correct
2 Correct 8633 ms 21336 KB Output is correct
3 Correct 5777 ms 21196 KB Output is correct
4 Correct 7500 ms 20068 KB Output is correct
5 Correct 7426 ms 20068 KB Output is correct
6 Correct 5781 ms 18528 KB Output is correct
7 Correct 5604 ms 18528 KB Output is correct
8 Correct 5777 ms 18528 KB Output is correct
9 Correct 5594 ms 18528 KB Output is correct
10 Correct 5483 ms 20068 KB Output is correct
11 Correct 4703 ms 20068 KB Output is correct
12 Correct 5664 ms 20068 KB Output is correct
13 Correct 4960 ms 20068 KB Output is correct
14 Correct 3994 ms 20068 KB Output is correct
15 Correct 7338 ms 21900 KB Output is correct
16 Correct 5618 ms 20068 KB Output is correct
17 Correct 5749 ms 20068 KB Output is correct
18 Correct 5592 ms 20068 KB Output is correct
19 Execution timed out 9000 ms 22176 KB Program timed out
20 Halted 0 ms 0 KB -