oj.uz

Submission #428008

# Submission time Handle Problem Language Result Execution time Memory
428008 2021-06-15T07:12:15 Z pliam Dancing Elephants (IOI11_elephants) C++14
100 / 100
 7339 ms 18624 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 150005
#define MAXNUM 400//bucket number
#define MAXBUCK 800//max bucket size limit

int n,l,buck;//buck=max bucket size
vector<int> elephants[MAXNUM];
multiset<int> all_e;//all elephant positions
int dp[MAXNUM][MAXBUCK];
int last[MAXNUM][MAXBUCK];
int count_buck,count_q;
int* pos_e;

void build_buck(int i){//build bucket i
  int la=elephants[i].size()-1;
  for(int pos=elephants[i].size()-1;pos>=0;pos--){
    if(la==elephants[i].size()-1){
      dp[i][pos]=1;
      last[i][pos]=elephants[i][pos]+l;
    }
    else{
      dp[i][pos]=1+dp[i][la+1];
      last[i][pos]=last[i][la+1];
    }
    if(pos==0) continue;
    while(elephants[i][la]>elephants[i][pos-1]+l){
      la--;
    }
  }
}

void erase_buck(int i,int val){
  elephants[i].erase(lower_bound(elephants[i].begin(),elephants[i].end(),val));
  build_buck(i);
}

void insert_buck(int i,int val){
  elephants[i].insert(lower_bound(elephants[i].begin(),elephants[i].end(),val),val);
  build_buck(i);
}

int find_buck(int val){
  int pos=0;
  while(pos<count_buck&&(elephants[pos].empty()||elephants[pos].back()<val)) pos++;
  if(pos==count_buck) pos--;
  return pos;
}

void build_sqrt(){
  for(int b=0;b<count_buck;b++) elephants[b].clear();
  count_buck=0;
  auto it_pos=all_e.begin();
  for(int pos=0;pos<all_e.size();pos++,it_pos++){
    int b=pos/buck;
    elephants[b].insert(lower_bound(elephants[b].begin(),elephants[b].end(),*it_pos),*it_pos);
    count_buck=max(count_buck,b+1);
  }
  for(int b=0;b<count_buck;b++){
    build_buck(b);
  }
}

int query(){
  int first_pos=0;
  int ans=0;
  for(int b=0;b<count_buck;b++){
    if(elephants[b].empty()||elephants[b].back()<first_pos) continue;
    int pos=lower_bound(elephants[b].begin(),elephants[b].end(),first_pos)-elephants[b].begin();
    ans+=dp[b][pos];
    first_pos=last[b][pos]+1;
  }
  return ans;
}

void init(int N, int L, int X[])
{
  n = N;
  l=L;
  pos_e=X;
  buck=sqrt(N);
  for(int i=0;i<N;i++){
    all_e.insert(X[i]);
  }
  build_sqrt();
}

int update(int i, int y)
{
  count_q++;
  if(count_q>buck){
    build_sqrt();//rebuilding
    count_q=0;//reset counter
  }
  all_e.erase(all_e.find(pos_e[i]));
  all_e.insert(y);
  erase_buck(find_buck(pos_e[i]),pos_e[i]);
  insert_buck(find_buck(y),y);
  pos_e[i]=y;

  return query();
}

Compilation message

elephants.cpp: In function 'void build_buck(int)':
elephants.cpp:19:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     if(la==elephants[i].size()-1){
      |        ~~^~~~~~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void build_sqrt()':
elephants.cpp:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(int pos=0;pos<all_e.size();pos++,it_pos++){
      |                 ~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 362 ms 3292 KB Output is correct
8 Correct 435 ms 3812 KB Output is correct
9 Correct 614 ms 6652 KB Output is correct
10 Correct 598 ms 6444 KB Output is correct
11 Correct 603 ms 6384 KB Output is correct
12 Correct 961 ms 6464 KB Output is correct
13 Correct 638 ms 6212 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 362 ms 3292 KB Output is correct
8 Correct 435 ms 3812 KB Output is correct
9 Correct 614 ms 6652 KB Output is correct
10 Correct 598 ms 6444 KB Output is correct
11 Correct 603 ms 6384 KB Output is correct
12 Correct 961 ms 6464 KB Output is correct
13 Correct 638 ms 6212 KB Output is correct
14 Correct 589 ms 4604 KB Output is correct
15 Correct 719 ms 4876 KB Output is correct
16 Correct 1649 ms 7140 KB Output is correct
17 Correct 1823 ms 8948 KB Output is correct
18 Correct 2049 ms 8884 KB Output is correct
19 Correct 1000 ms 9132 KB Output is correct
20 Correct 1691 ms 8944 KB Output is correct
21 Correct 1782 ms 8932 KB Output is correct
22 Correct 1038 ms 8528 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 362 ms 3292 KB Output is correct
8 Correct 435 ms 3812 KB Output is correct
9 Correct 614 ms 6652 KB Output is correct
10 Correct 598 ms 6444 KB Output is correct
11 Correct 603 ms 6384 KB Output is correct
12 Correct 961 ms 6464 KB Output is correct
13 Correct 638 ms 6212 KB Output is correct
14 Correct 589 ms 4604 KB Output is correct
15 Correct 719 ms 4876 KB Output is correct
16 Correct 1649 ms 7140 KB Output is correct
17 Correct 1823 ms 8948 KB Output is correct
18 Correct 2049 ms 8884 KB Output is correct
19 Correct 1000 ms 9132 KB Output is correct
20 Correct 1691 ms 8944 KB Output is correct
21 Correct 1782 ms 8932 KB Output is correct
22 Correct 1038 ms 8528 KB Output is correct
23 Correct 4521 ms 17964 KB Output is correct
24 Correct 5101 ms 17964 KB Output is correct
25 Correct 4149 ms 17964 KB Output is correct
26 Correct 4454 ms 17968 KB Output is correct
27 Correct 4633 ms 17820 KB Output is correct
28 Correct 882 ms 5700 KB Output is correct
29 Correct 813 ms 5720 KB Output is correct
30 Correct 936 ms 5696 KB Output is correct
31 Correct 856 ms 5696 KB Output is correct
32 Correct 3654 ms 17476 KB Output is correct
33 Correct 4136 ms 16732 KB Output is correct
34 Correct 3566 ms 17636 KB Output is correct
35 Correct 4151 ms 18624 KB Output is correct
36 Correct 4621 ms 17372 KB Output is correct
37 Correct 6442 ms 18508 KB Output is correct
38 Correct 4003 ms 16620 KB Output is correct
39 Correct 3595 ms 17644 KB Output is correct
40 Correct 3954 ms 16636 KB Output is correct
41 Correct 7057 ms 17512 KB Output is correct
42 Correct 7339 ms 17628 KB Output is correct