Submission #263042

#	Time	Username	Problem	Language	Result	Execution time	Memory
263042		dantoh000	Dancing Elephants (IOI11_elephants)	C++14	26 / 100	9070 ms	5392 KiB

elephants

#include <bits/stdc++.h>
#define K 500
using namespace std;
#include "elephants.h"

int n, l, x[150005];
struct BUCKET{
    int a[150005], ct[150005], r[150005], sz;
    void comp(){
        int k = sz-1;
        for (int i = sz-1; i >= 0; i--){
            while (k > i && a[k-1] - a[i] > l) k--;
            if (a[sz-1] - a[i] <= l){
                ct[i] = 1; r[i] = a[i]+l;
            }
            else ct[i] = ct[k]+1, r[i] = r[k];
            //printf("%d -> %d: ct = %d, r = %d\n",a[i],a[k],ct[i],r[i]);
        }
    }
} bk[305];
void init(int N, int L, int X[])
{
  n = N;
  l = L;
  for (int i = 0; i < n; i++) x[i] = X[i];
  for (int i = 0; i <= n/K; i++){
        bk[i].sz = 0;
        for (int j = i*K; j < min((i+1)*K,n); j++){
            bk[i].a[j%K] = x[j];
            bk[i].sz++;
        }
        bk[i].comp();
  }
}
void rebuild_all(){
    int N = 0;
    for (int i = 0; i <= n/K; i++){
        for (int j = 0; j < bk[i].sz; j++){
            x[N++] = bk[i].a[j];
        }
    }
    for (int i = 0; i <= n/K; i++){
        bk[i].sz = 0;
        for (int j = i*K; j < min((i+1)*K,n); j++){
            bk[i].a[j%K] = x[j];
            bk[i].sz++;
        }
        bk[i].comp();
    }
}

void add(int x){
    //printf("adding %d\n",x);
    for (int i = 0; i <= n/K; i++){
        if (bk[i].sz == 0) continue;
        if ((bk[i].a[0] > x) || i == (n-1)/K || (bk[i].a[0] <= x && x < bk[i+1].a[0]) ){
            //printf("adding to bucket %d\n",i);
            if (bk[i].a[0] > x){
                //printf("position %d\n",0);
                for (int k = bk[i].sz-1; k >= 0; k--){
                    bk[i].a[k+1] = bk[i].a[k];
                }
                bk[i].a[0] = x;

            }
            else{
                for (int j = 0; j < bk[i].sz; j++){
                    if ((bk[i].a[j] <= x && x < bk[i].a[j+1]) || j+1 == bk[i].sz){
                        //printf("position %d\n",j+1);
                        for (int k = bk[i].sz-1; k >= j+1; k--){
                            bk[i].a[k+1] = bk[i].a[k];
                        }
                        bk[i].a[j+1] = x;
                        break;
                    }
                }
            }
            bk[i].sz++;
            bk[i].comp();
            break;
        }
    }
}
void del(int x){
    //printf("deleting %d\n",x);
    for (int i = 0; i <= n/K; i++){
        if (bk[i].sz == 0) continue;
        if (bk[i].a[0] <= x && x <= bk[i].a[bk[i].sz-1]){
            //printf("deleting from bucket %d\n",i);
            for (int j = 0; j < bk[i].sz; j++){
                if (bk[i].a[j] == x){
                    //printf("position %d\n",j);
                    for (int k = j; k < bk[i].sz; k++){
                        bk[i].a[k] = bk[i].a[k+1];
                    }
                    break;
                }
            }
            bk[i].a[bk[i].sz] = 0;
            bk[i].sz--;
            bk[i].comp();
            break;
        }
    }
}
int solve(){
    //printf("solving\n");
    int curpos = -1;
    int ans = 0;
    for (int i = 0; i <= n/K; i++){
        if (bk[i].sz == 0) continue;
        //printf("%d ",curpos);
        int nx = upper_bound(bk[i].a, bk[i].a+bk[i].sz,curpos) - bk[i].a;
        //printf("add %d to %d\n",bk[i].ct[nx],ans);
        ans += bk[i].ct[nx];
        curpos = bk[i].r[nx];
    }
    return ans;

}
void debug(){
    int last = -1;
    for (int i = 0; i <= n/K; i++){
        //printf("bucket %d: ",i);
        for (int j = 0; j <  bk[i].sz; j++){
           // printf("%d ",bk[i].a[j]);
            assert(bk[i].a[j] >= last);
            last= bk[i].a[j];

        }
        // printf("\n");
    }
}
int numQ = 0;
int update(int i, int y)
{
    //printf("update %d %d->%d\n",i,x[i],y);
    //if (++numQ == K){
    //    rebuild_all();
    //    numQ = 0;
    //}
    del(x[i]);
    x[i] = y;
    add(x[i]);
    debug();
    return solve();
}

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