Submission #110620

#	Time	Username	Problem	Language	Result	Execution time	Memory
110620		m3r8	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	5911 ms	14840 KiB

elephants

#include "elephants.h"
#include <stdio.h>
#include <string.h>
#include <cmath>
#include <algorithm>



typedef struct ele{
  int bc;
  int end;
  int bf;
  int pos;
  int id;
} ele;
ele bucket[1000][1000];
int sz[1000];
int anzB;
int n;
int l;
int sele[200000];
int bele[200000];
int ih[200000];
void calcB(int idx){
  int s = sz[idx];  
  int tmp = s-1;
  for(int i = s-1;i>=0;i--){
    if(bucket[idx][i].bf == -1 && (i == s-1 || bucket[idx][i+1].bf == -1)){
      bucket[idx][i].end = bucket[idx][i].pos + l;
      bucket[idx][i].bc = 1;
    }else{
      int b = bucket[idx][i].bf;
      if(b == -1){
        b = bucket[idx][i+1].bf;  
        bucket[idx][i].bf = b;
      };
      bucket[idx][i].end = bucket[idx][b].end;
      bucket[idx][i].bc = bucket[idx][b].bc + 1;
    };
    while(tmp != -1 && bucket[idx][tmp].pos +l >= bucket[idx][i].pos){
      tmp--;
    };
    if(tmp != -1){
      bucket[idx][tmp].bf = i;  
    };
  };
};
void delE(int idx, int id){
  int s = sz[idx]-1;  
  int tmp = bucket[idx][s].pos;
  int itmp = bucket[idx][s].id;
  while(s != 0 && itmp != id){
    std::swap(tmp,bucket[idx][s-1].pos);
    std::swap(itmp,bucket[idx][s-1].id);
    s--;
  };
  sz[idx]--;
  for(int i = 0;i<sz[idx];i++){
    bucket[idx][i].bf = -1; 
  };
  calcB(idx);
};
void insertE(int idx, int id, int pos){
  bele[id] = idx;
  int s = sz[idx]-1;  
  int tmp = s > -1 ?bucket[idx][s].pos:0;
  int itmp = s > -1 ?bucket[idx][s].id:0;
  while(s != -1 && tmp > pos){
    std::swap(tmp,bucket[idx][s+1].pos);
    std::swap(itmp,bucket[idx][s+1].id);
    s--;
    tmp = s > -1 ?bucket[idx][s].pos:0;
    itmp = s > -1 ?bucket[idx][s].id:0;
  //  printf("%d %d %d\n",tmp,pos,s);
  };
  bucket[idx][s+1].pos = pos;
  bucket[idx][s+1].id = id;
  sz[idx]++;
  for(int i = 0;i<sz[idx];i++){
    bucket[idx][i].bf = -1; 
  };
  calcB(idx);
};
int findN(int idx, int &aktP){
  int idxR = sz[idx]-1;
  int idxL = 0;
  if(bucket[idx][idxR].pos <= aktP){
    //printf("%d %d %d\n",idx,idxR,bucket[idx][idxR].pos);
    return 0;
  }else{
    while(idxR > idxL){
      int idxM = (idxR + idxL)/2;
      if(bucket[idx][idxM].pos <= aktP){
        idxL = idxM+1;  
      }else{
        idxR = idxM;  
      };
    };
    aktP = bucket[idx][idxL].end;
    return bucket[idx][idxL].bc;
  };  
};
int querry(){
  int aktP = 0;
  int aktC = 0;
  int first = 0;
  for(int i = 0;i<anzB;i++){
    if(sz[i]){
      if(!first){
        aktC += bucket[i][0].bc;  
        aktP += bucket[i][0].end;  
        first = 1;
        //printf("%d %d\n",aktC,aktP);
      }else{
        //printf("%d %d geil\n",sz[i],anzB);
        aktC += findN(i,aktP);  
        //printf("%d %d\n",aktC,aktP);
      };
    };
  };  
  return aktC;
};
void makeB(){
  anzB = std::ceil(std::sqrt(n));   
  int cnt = 0;
  int cnt1 = 0;
  for(int i = 0;i<anzB;i++){
    sz[i] = 0;  
  };
  for(int i = 0;i<n;i++){
    bucket[cnt][cnt1].pos = sele[i];
    bucket[cnt][cnt1].bf = -1;
    bucket[cnt][cnt1++].id = ih[i];
    bele[ih[i]] = cnt;
    if(cnt1 == anzB){
      sz[cnt] = cnt1;
      calcB(cnt);
      cnt1 = 0;  
      cnt++;
    };
  };
  if(cnt1){
    sz[cnt] = cnt1;
    calcB(cnt);
  };
};
void makeN(){
  int cnt = 0;
  for(int i = 0;i<anzB;i++){
    for(int j = 0;j<sz[i];j++){
      ih[cnt] = bucket[i][j].id;  
      sele[cnt] = bucket[i][j].pos;  
      cnt++;
    };
  };  
  makeB();
};
void printB(){
  for(int i = 0;i<anzB;i++){
    if(sz[i] == 0){
      printf("Empty");  
    };
    for(int j = 0;j<sz[i];j++){
      printf("(%d, %d, %d, %d, %d) ",bucket[i][j].pos,bucket[i][j].id,bucket[i][j].bc,bucket[i][j].end,bucket[i][j].bf);
      puts("");
    };
    puts("");
  };  
  puts("");
  puts("");
};

void init(int N, int L, int X[])
{
  n = N;
  l = L;
  for(int i = 0;i<n;i++){
    sele[i] = X[i];   
    ih[i] = i;
  };
  makeB();
  //printB();
}
int up = 0;

int update(int i, int y)
{
  int idx = bele[i];
  delE(idx,i);
  //printf("Delete\n");
  //printB();
  int ins = 0;
  for(int j = 0;j<anzB&&!ins;j++){
    if(sz[j]){
      if(bucket[j][sz[j]-1].pos >= y){
        if(bucket[j][0].pos >= y && j != 0){
          insertE(j-1,i,y);
        }else{
          insertE(j,i,y);
        };
        ins = 1;
      };
    };  
  };
  if(!ins){
    insertE(anzB-1,i,y);
  };
  //printf("querry\n");
  //printB();
  int erg = querry(); 
  if(up == anzB){
    makeN();  
    //printf("new\n");
    //printB();
    up = 0;
  }else{
    up++;  
  };
  return erg;
}

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