Submission #13795

#	Time	Username	Problem	Language	Result	Execution time	Memory
13795		gs14004	Dancing Elephants (IOI11_elephants)	C++14	Compilation error	0 ms	0 KiB

elephants

#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;

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();
}

int main(){
    int n,l,m,p[150005];
    scanf("%d %d %d",&n,&l,&m);
    for (int i=0; i<n; i++) {
        scanf("%d",&p[i]);
    }
    init(n,l,p);
    for (int i=0; i<m; i++) {
        int a,b;
        scanf("%d %d",&a,&b);
        printf("%d\n",update(a,b));
    }
}

Compilation message (stderr)

elephants.cpp: In function ‘void make_arr()’:
elephants.cpp:28:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=0; j<bucket[i].size(); j++) {
                        ^
elephants.cpp: In function ‘void bucket_label(int)’:
elephants.cpp:40:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(pt == bucket[bnum].size()){
               ^
elephants.cpp: In function ‘void bucket_erase(int, int)’:
elephants.cpp:69:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=pos; i<bucket[bnum].size()-1; i++) {
                      ^
elephants.cpp: In function ‘int main()’:
elephants.cpp:156:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d",&n,&l,&m);
                               ^
elephants.cpp:158:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&p[i]);
                          ^
elephants.cpp:163:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&a,&b);
                             ^
/tmp/ccnFu56e.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccn7Xg3z.o:elephants.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status