Submission #5041

#	Time	Username	Problem	Language	Result	Execution time	Memory
5041		cki86201	Dancing Elephants (IOI11_elephants)	C++98	100 / 100	5844 ms	21744 KiB

elephants

#include "elephants.h"
#include <math.h>

const int N_ = 150050;
const int SN = 400;

int bk_sz, counter, L, N;
int D[N_], tmp[N_];

struct Group{
    Group(){
        for(int i=0;i<SN*2;i++)w[i]=c[i]=en[i]=0;
        sz=0;
    }
    int w[SN*2], en[SN*2], c[SN*2];
    int sz;
    void fix(){
        int s;
        for(s=sz-1;s!=-1 && w[sz-1] - w[s] <= L;s--)c[s] = 1, en[s] = w[s] + L;
        for(int e = sz-1;s!=-1;s--){
            while(w[e] - w[s] > L)e--;
            c[s] = c[e+1] + 1;
            en[s] = en[e+1];
        }
    }
    void update(int v){
        int i, ins;
        for(ins=0;w[ins]<=v && ins!=sz;ins++);
        sz++;
        for(i=sz-1;i>ins;i--)w[i] = w[i-1];
        w[ins] = v;
        fix();
    }
    void del(int v){
        int i, d=0;
        while(w[d] != v)d++;
        sz--;
        for(i=d;i<sz;i++)w[i] = w[i+1];
        w[sz] = 0;
        fix();
    }
};

struct elephants{
    elephants(){
        for(int i=0;i<SN;i++)gr[i] = Group();
        sz=0;
    }
    Group gr[SN+10];
    int sz;
    void init(){
        int i,now=0,cnt=0;
        for(i=0;i<N;i++){
            if(cnt == bk_sz)gr[now].sz = cnt, gr[now++].fix(), cnt = 0;
            gr[now].w[cnt++] = D[i];
        }
        gr[now].sz = cnt, gr[now].fix(), sz = now + 1;
    }
    void fix(){
        int len = 0;
        for(int i=0;i<sz;i++)for(int j=0;j<gr[i].sz;j++)tmp[len++] = gr[i].w[j];
        int now=0,cnt=0;
        for(int i=0;i<N;i++){
            if(cnt == bk_sz)gr[now].sz = cnt, gr[now++].fix(), cnt = 0;
            gr[now].w[cnt++] = tmp[i];
        }
        gr[now].sz = cnt, gr[now].fix(), sz = now + 1;
    }
    void update(int v){
        int ins=1;
        for(;ins<sz && gr[ins].w[0] <= v;ins++);
        gr[ins-1].update(v);
    }
    void del(int v){
        int d = 0;
        for(;gr[d].sz && gr[d].w[0] <= v;d++);
        gr[d-1].del(v);
    }
    int get_ans(){
        int i, ret = 0, now, en = -1;
        for(i=0;i<sz;i++){
            int s=0, e=gr[i].sz-1;
            if(gr[i].w[e] <= en)continue;
            while(s<=e){
                int m=(s+e)>>1;
                if(gr[i].w[m] > en)now=m, e=m-1;
                else s=m+1;
            }
            ret += gr[i].c[now];
            en = gr[i].en[now];
        }
        return ret;
    }
};

elephants Ep;

void init(int N, int L, int X[])
{
	::N = N, ::L = L;
	bk_sz = sqrt(N);
	for(int i=0;i<N;i++)D[i] = X[i];
	Ep.init();
}

int update(int i, int y)
{
	Ep.update(y);
	Ep.del(D[i]);
	D[i] = y;
	if(++counter == bk_sz)Ep.fix(), counter = 0;
	return Ep.get_ans();
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3