제출 #1013909

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1013909		vjudge1	코끼리 (Dancing Elephants) (IOI11_elephants)	C++17	100 / 100	1889 ms	14764 KiB

elephants

#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
int n,sz=500,arr[150100],cnt,num,len;
vector<int>buckets[310],need[310],lst[310];
void recalc(int id){
  if(buckets[id].empty())return;
  need[id].resize(buckets[id].size(),0);
  lst[id].resize(buckets[id].size(),0);
  int k=buckets[id].size()-1,l=buckets[id].back();
  while(k>=0&&buckets[id][k]>=l-len)  
    lst[id][k]=buckets[id][k]+len,need[id][k]=1,k--;
  int x=buckets[id].size()-1;
  while(k>=0){
    while(buckets[id][x-1]>buckets[id][k]+len)x--;
    lst[id][k]=lst[id][x];
    need[id][k]=need[id][x]+1;
    k--;
  }
}
void recons(){
  vector<int>thingys;
  for(int i=0;i<num;buckets[i++].clear())
    for(auto j:buckets[i])  
      thingys.push_back(j);
  int x=thingys.size();
  for(int i=0;i<num;recalc(i++))
    for(int j=i*sz;j<min(i*sz+sz,x);j++)
      buckets[i].push_back(thingys[j]);
}
int gedans(){
  int pew=-1,cnt=0;
  for(int i=0;i<num;i++){
    int x=upper_bound(all(buckets[i]),pew)-buckets[i].begin();
    if(x==buckets[i].size())continue;
    cnt+=need[i][x];
    pew=lst[i][x];
  }
  return cnt;
}
void init(int N, int L, int X[]) {
  n = N;
  len=L;
  for(int i=0;i<N;i++)
    buckets[0].push_back(arr[i]=X[i]);
  num=(n+sz-1)/sz;
  recons();
}
int update(int i, int y) {
  cnt++;
  int id=0;
  for(int x=0;x<num;x++)
    if(buckets[x].size()&&
      buckets[x].back()>=arr[i]){
      id=x; break;}
  buckets[id].erase(lower_bound(all(buckets[id]),arr[i]));
  recalc(id); arr[i]=y;
  id=num-1;
  for(int i=0;i<num;i++)
    if(buckets[i].size()&&y<=buckets[i].back()){
      id=i;break;}
  buckets[id].insert(lower_bound(all(buckets[id]),y),y);
  recalc(id);
  if(cnt==sz)
    cnt=0,recons();
  return gedans();
}

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

elephants.cpp: In function 'int gedans()':
elephants.cpp:36:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     if(x==buckets[i].size())continue;
      |        ~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3