oj.uz

Submission #5041

# Submission time Handle Problem Language Result Execution time Memory
5041 2014-01-29T07:57:58 Z cki86201 Dancing Elephants (IOI11_elephants) C++
100 / 100
 5844 ms 21744 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 21744 KB Output is correct
2 Correct 0 ms 21744 KB Output is correct
3 Correct 0 ms 21744 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 21744 KB Output is correct
2 Correct 0 ms 21744 KB Output is correct
3 Correct 0 ms 21744 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 21744 KB Output is correct
2 Correct 336 ms 21744 KB Output is correct
3 Correct 536 ms 21744 KB Output is correct
4 Correct 464 ms 21744 KB Output is correct
5 Correct 352 ms 21744 KB Output is correct
6 Correct 704 ms 21744 KB Output is correct
7 Correct 468 ms 21744 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 21744 KB Output is correct
2 Correct 556 ms 21744 KB Output is correct
3 Correct 1108 ms 21744 KB Output is correct
4 Correct 1432 ms 21744 KB Output is correct
5 Correct 1488 ms 21744 KB Output is correct
6 Correct 1056 ms 21744 KB Output is correct
7 Correct 1508 ms 21744 KB Output is correct
8 Correct 1424 ms 21744 KB Output is correct
9 Correct 1012 ms 21744 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5216 ms 21744 KB Output is correct
2 Correct 5360 ms 21744 KB Output is correct
3 Correct 4364 ms 21744 KB Output is correct
4 Correct 4912 ms 21744 KB Output is correct
5 Correct 4956 ms 21744 KB Output is correct
6 Correct 600 ms 21744 KB Output is correct
7 Correct 536 ms 21744 KB Output is correct
8 Correct 600 ms 21744 KB Output is correct
9 Correct 600 ms 21744 KB Output is correct
10 Correct 4164 ms 21744 KB Output is correct
11 Correct 3144 ms 21744 KB Output is correct
12 Correct 4476 ms 21744 KB Output is correct
13 Correct 3184 ms 21744 KB Output is correct
14 Correct 1220 ms 21744 KB Output is correct
15 Correct 5164 ms 21744 KB Output is correct
16 Correct 4632 ms 21744 KB Output is correct
17 Correct 4396 ms 21744 KB Output is correct
18 Correct 4336 ms 21744 KB Output is correct
19 Correct 5728 ms 21744 KB Output is correct
20 Correct 5844 ms 21744 KB Output is correct