oj.uz

Submission #116757

# Submission time Handle Problem Language Result Execution time Memory
116757 2019-06-13T17:25:15 Z dragonslayerit Dancing Elephants (IOI11_elephants) C++14
50 / 100
 1170 ms 154084 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.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,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

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:116: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 2 ms 384 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 2 ms 384 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
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 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 191 ms 13372 KB Output is correct
8 Correct 206 ms 18296 KB Output is correct
9 Correct 325 ms 49016 KB Output is correct
10 Correct 620 ms 152760 KB Output is correct
11 Correct 630 ms 154084 KB Output is correct
12 Correct 638 ms 65008 KB Output is correct
13 Correct 625 ms 153832 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 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 191 ms 13372 KB Output is correct
8 Correct 206 ms 18296 KB Output is correct
9 Correct 325 ms 49016 KB Output is correct
10 Correct 620 ms 152760 KB Output is correct
11 Correct 630 ms 154084 KB Output is correct
12 Correct 638 ms 65008 KB Output is correct
13 Correct 625 ms 153832 KB Output is correct
14 Correct 396 ms 88600 KB Output is correct
15 Correct 340 ms 34220 KB Output is correct
16 Correct 1031 ms 100200 KB Output is correct
17 Correct 1170 ms 130884 KB Output is correct
18 Incorrect 54 ms 7288 KB Output isn't correct
19 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 2 ms 384 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 191 ms 13372 KB Output is correct
8 Correct 206 ms 18296 KB Output is correct
9 Correct 325 ms 49016 KB Output is correct
10 Correct 620 ms 152760 KB Output is correct
11 Correct 630 ms 154084 KB Output is correct
12 Correct 638 ms 65008 KB Output is correct
13 Correct 625 ms 153832 KB Output is correct
14 Correct 396 ms 88600 KB Output is correct
15 Correct 340 ms 34220 KB Output is correct
16 Correct 1031 ms 100200 KB Output is correct
17 Correct 1170 ms 130884 KB Output is correct
18 Incorrect 54 ms 7288 KB Output isn't correct
19 Halted 0 ms 0 KB -