oj.uz

Submission #116753

# Submission time Handle Problem Language Result Execution time Memory
116753 2019-06-13T17:18:50 Z dragonslayerit Dancing Elephants (IOI11_elephants) C++14
26 / 100
 9000 ms 93532 KB 
#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);
      if(blocks[i].pos.size()>=BLK_SIZE*2){
	blocks.insert(blocks.begin()+i,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

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:100:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int k=BLK_SIZE;k<blocks[i].pos.size();k++){
                     ~^~~~~~~~~~~~~~~~~~~~~
elephants.cpp:117:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<blocks.size();i++){
               ~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 203 ms 2232 KB Output is correct
8 Correct 208 ms 2612 KB Output is correct
9 Correct 213 ms 3804 KB Output is correct
10 Execution timed out 9052 ms 93532 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 203 ms 2232 KB Output is correct
8 Correct 208 ms 2612 KB Output is correct
9 Correct 213 ms 3804 KB Output is correct
10 Execution timed out 9052 ms 93532 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 203 ms 2232 KB Output is correct
8 Correct 208 ms 2612 KB Output is correct
9 Correct 213 ms 3804 KB Output is correct
10 Execution timed out 9052 ms 93532 KB Time limit exceeded
11 Halted 0 ms 0 KB -