oj.uz

Submission #116758

# Submission time Handle Problem Language Result Execution time Memory
116758 2019-06-13T17:26:18 Z dragonslayerit Dancing Elephants (IOI11_elephants) C++14
100 / 100
 2338 ms 12856 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+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

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.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 2 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 2 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 2 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 218 ms 1488 KB Output is correct
8 Correct 229 ms 1536 KB Output is correct
9 Correct 226 ms 2604 KB Output is correct
10 Correct 217 ms 2916 KB Output is correct
11 Correct 232 ms 2928 KB Output is correct
12 Correct 374 ms 2820 KB Output is correct
13 Correct 268 ms 3048 KB Output is correct

Subtask #4
47.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 2 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 218 ms 1488 KB Output is correct
8 Correct 229 ms 1536 KB Output is correct
9 Correct 226 ms 2604 KB Output is correct
10 Correct 217 ms 2916 KB Output is correct
11 Correct 232 ms 2928 KB Output is correct
12 Correct 374 ms 2820 KB Output is correct
13 Correct 268 ms 3048 KB Output is correct
14 Correct 208 ms 2200 KB Output is correct
15 Correct 346 ms 2088 KB Output is correct
16 Correct 652 ms 3060 KB Output is correct
17 Correct 661 ms 3932 KB Output is correct
18 Correct 684 ms 3472 KB Output is correct
19 Correct 365 ms 5112 KB Output is correct
20 Correct 648 ms 5812 KB Output is correct
21 Correct 607 ms 5664 KB Output is correct
22 Correct 475 ms 5536 KB Output is correct

Subtask #5
3.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 2 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 218 ms 1488 KB Output is correct
8 Correct 229 ms 1536 KB Output is correct
9 Correct 226 ms 2604 KB Output is correct
10 Correct 217 ms 2916 KB Output is correct
11 Correct 232 ms 2928 KB Output is correct
12 Correct 374 ms 2820 KB Output is correct
13 Correct 268 ms 3048 KB Output is correct
14 Correct 208 ms 2200 KB Output is correct
15 Correct 346 ms 2088 KB Output is correct
16 Correct 652 ms 3060 KB Output is correct
17 Correct 661 ms 3932 KB Output is correct
18 Correct 684 ms 3472 KB Output is correct
19 Correct 365 ms 5112 KB Output is correct
20 Correct 648 ms 5812 KB Output is correct
21 Correct 607 ms 5664 KB Output is correct
22 Correct 475 ms 5536 KB Output is correct
23 Correct 1955 ms 11472 KB Output is correct
24 Correct 2021 ms 11616 KB Output is correct
25 Correct 1671 ms 11504 KB Output is correct
26 Correct 1556 ms 12836 KB Output is correct
27 Correct 1606 ms 10736 KB Output is correct
28 Correct 1281 ms 5196 KB Output is correct
29 Correct 1209 ms 5228 KB Output is correct
30 Correct 1301 ms 5276 KB Output is correct
31 Correct 1237 ms 5332 KB Output is correct
32 Correct 1945 ms 12352 KB Output is correct
33 Correct 1702 ms 11688 KB Output is correct
34 Correct 1617 ms 12428 KB Output is correct
35 Correct 1620 ms 12856 KB Output is correct
36 Correct 1897 ms 12284 KB Output is correct
37 Correct 1820 ms 11976 KB Output is correct
38 Correct 1885 ms 11460 KB Output is correct
39 Correct 1633 ms 10572 KB Output is correct
40 Correct 1834 ms 11460 KB Output is correct
41 Correct 2282 ms 12004 KB Output is correct
42 Correct 2338 ms 12084 KB Output is correct