Submission #116758

#	Time	Username	Problem	Language	Result	Execution time	Memory
116758		dragonslayerit	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	2338 ms	12856 KiB

elephants

#include "elephants.h"
#include <vector>
#include <algorithm>
#include <cstdio>

const int INF=1e9+7;
const int BLK_SIZE=400;
const int PERIOD=700;

int n;
int l;
int xs[150005];
int ys[150005];

struct Block{
  std::vector<int> pos;
  std::vector<int> reach;
  std::vector<int> jumps;
  void recalc(){
    reach.resize(pos.size());
    jumps.resize(pos.size());
    int j=pos.size();
    for(int i=(int)pos.size()-1;i>=0;i--){
      while(pos[j-1]>pos[i]+l) j--;
      if(j==(int)pos.size()){
	reach[i]=pos[i]+l;
	jumps[i]=1;
      }else{
	reach[i]=reach[j];
	jumps[i]=jumps[j]+1;
      }
    }
    /*
    fprintf(stderr,"BLOCK\n");
    for(int i=0;i<pos.size();i++){
      fprintf(stderr,"%d: reach %d, jump %d\n",pos[i],reach[i],jumps[i]);
    }
    */
  }
  void apply(int& x,int& cnt){
    auto it=std::upper_bound(pos.begin(),pos.end(),x);
    if(it==pos.end()) return;
    int i=it-pos.begin();
    cnt+=jumps[i];
    x=reach[i];
  }
};
std::vector<Block*> blocks;

void rebuild(){
  std::copy(xs,xs+n,ys);
  std::sort(ys,ys+n);
  blocks.clear();
  for(int i=0;i<n;i++){
    if(i%BLK_SIZE==0){
      blocks.push_back(new Block());
    }
    blocks.back()->pos.push_back(ys[i]);
  }
  for(int i=0;i<blocks.size();i++){
    blocks[i]->recalc();
  }
}

void init(int N, int L, int X[])
{
  n=N;
  l=L;
  for(int i=0;i<N;i++){
    xs[i]=X[i];
  }
  rebuild();
}

int current_query=0;

int update(int index, int new_val)
{
  int old_val=xs[index];
  xs[index]=new_val;

  //erase old_val
  for(int i=0;i<blocks.size();i++){
    if(blocks[i]->pos.back()>=old_val){
      blocks[i]->pos.erase(std::lower_bound(blocks[i]->pos.begin(),blocks[i]->pos.end(),old_val));
      if(!blocks[i]->pos.empty()){
	blocks[i]->recalc();
      }else{
	delete blocks[i];
	blocks.erase(blocks.begin()+i);
      }
      break;
    }
  }
  //insert new_val
  for(int i=0;i<blocks.size();i++){
    if(i==blocks.size()-1||blocks[i+1]->pos.front()>new_val){
      blocks[i]->pos.insert(std::lower_bound(blocks[i]->pos.begin(),blocks[i]->pos.end(),new_val),new_val);
      if(blocks[i]->pos.size()>=BLK_SIZE*2){
	blocks.insert(blocks.begin()+i+1,new Block());
	for(int k=BLK_SIZE;k<blocks[i]->pos.size();k++){
	  blocks[i+1]->pos.push_back(blocks[i]->pos[k]);
	}
	blocks[i]->pos.resize(BLK_SIZE);
	blocks[i+1]->recalc();
      }
      blocks[i]->recalc();
      break;
    }
  }
  /*
  if(++current_query%PERIOD==0){
    rebuild();
  }
  */
  //rebuild();
  int pos=-INF,cnt=0;
  for(int i=0;i<blocks.size();i++){
    blocks[i]->apply(pos,cnt);
  }
  return cnt;
}

Compilation message (stderr)

elephants.cpp: In function 'void rebuild()':
elephants.cpp:60:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<blocks.size();i++){
               ~^~~~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:83:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<blocks.size();i++){
               ~^~~~~~~~~~~~~~
elephants.cpp:96:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<blocks.size();i++){
               ~^~~~~~~~~~~~~~
elephants.cpp:97:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(i==blocks.size()-1||blocks[i+1]->pos.front()>new_val){
        ~^~~~~~~~~~~~~~~~~
elephants.cpp:101:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int k=BLK_SIZE;k<blocks[i]->pos.size();k++){
                     ~^~~~~~~~~~~~~~~~~~~~~~
elephants.cpp:118:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<blocks.size();i++){
               ~^~~~~~~~~~~~~~

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