Submission #116620

#	Time	Username	Problem	Language	Result	Execution time	Memory
116620		dragonslayerit	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	4974 ms	6996 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.emplace_back();
    }
    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{
	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);
      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:95:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<blocks.size();i++){
               ~^~~~~~~~~~~~~~
elephants.cpp:96: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:107: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