제출 #428008

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
428008		pliam	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	100 / 100	7339 ms	18624 KiB

elephants

#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();
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3