oj.uz

Submission #13794

# Submission time Handle Problem Language Result Execution time Memory
13794 2015-04-01T15:15:32 Z gs14004 Dancing Elephants (IOI11_elephants) C++14
26 / 100
 9000 ms 20064 KB 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int U = 1; // 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++) {
            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 && b[i*B+pt-1] > b[j] + l) pt--;
            if(pt == piv){
                bucket[i][j-i*B].val = b[j];
                bucket[i][j-i*B].next = -1;
                bucket[i][j-i*B].cnt = 0;
            }
            else{
                bucket[i][j-i*B].val = b[j];
                if(bucket[i][pt].next == -1){
                    bucket[i][j-i*B].next = pt;
                }
                else{
                    bucket[i][j-i*B].next = bucket[i][pt].next;
                }
                bucket[i][j-i*B].cnt = bucket[i][pt].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; ) {
        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);
    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;
    // erase and delete in ordered set
    if(q_cnt == 0){
      //  make_arr();
        for (int i=0; i<n; i++) {
            b[i] = a[i];
        }
        sort(b,b+n);
        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
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9000 ms 18516 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9000 ms 18516 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9000 ms 20064 KB Program timed out
2 Halted 0 ms 0 KB -