oj.uz

Submission #13749

# Submission time Handle Problem Language Result Execution time Memory
13749 2015-03-31T14:39:22 Z gs14004 Dancing Elephants (IOI11_elephants) C++14
0 / 100
 97 ms 19476 KB 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int U = 1500; // 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 = 0;

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++) {
            a[piv++] = bucket[i][j].val;
        }
    }
}

void bucket_clear(){
    for (int i=0; i<sentinel; i++) {
        bucket[i].clear();
        int piv = min(n-i*B,B);
        int pt = piv;
        bucket[i].resize(piv);
        for (int j=i*B+piv-1; j>=i*B; j--) {
            while (pt && a[i*B+pt-1] > a[j] + l) pt--;
            if(pt == piv){
                bucket[i][j-i*B] = {a[j],-1,0};
            }
            else{
                bucket[i][j-i*B].val = a[j];
                if(bucket[i][pt-i*B].next == -1){
                    bucket[i][j-i*B].next = pt-i*B;
                }
                else{
                    bucket[i][j-i*B].next = bucket[i][pt-i*B].next;
                }
                bucket[i][j-i*B].cnt = bucket[i][pt-i*B].cnt + 1;
            }
        }
    }
}

void single_bucket_update(int buck_num, int pos, int val){
    
}

int query(){
    int pos = 0, ret = 0;
    for (int i=0; i<sentinel; ) {
        ret += bucket[i][pos].cnt + 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(upper_bound(bucket[new_buck].begin(),bucket[new_buck].end(),(elem){new_pos,0,0})
              != bucket[new_buck].end()) break;
            new_buck++;
        }
        if(new_buck == sentinel) break;
        i = new_buck;
        
        pos = (int)(upper_bound(bucket[new_buck].begin(),bucket[new_buck].end(),(elem){new_pos,0,0}) - bucket[new_buck].begin());
    }
    return ret;
}

void init(int N, int L, int* X){
    memcpy(a,X,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 piv = i;
    int pos = -1;
    for (int i=0; i*B<n; i++) {
        if(piv >= bucket[i].size()){
            piv -= bucket[i].size();
        }
        else{
            pos = i;
            break;
        }
    }
    single_bucket_update(pos,piv,y);*/
    
    if(1 || q_cnt == 0){
      //  make_arr();
        a[i] = y;
        sort(a,a+n);
        bucket_clear();
    }
    return query();
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 17792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 17792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 17932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 17932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 97 ms 19476 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -