Submission #1013882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013882		vjudge1	Dancing Elephants (IOI11_elephants)	C++17	26 / 100	15 ms	14940 KiB

elephants

#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
int n,sz=400,arr[150100],cnt,num,len;
vector<int>buckets[400],need[400],lst[400];
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;
  while(k>=0){
    int x=upper_bound(all(buckets[id]),buckets[id][k]+len)-buckets[id].begin();
    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);
  for(int i=0;i<num;recalc(i++))
    for(int j=i*sz;j<min(i*sz+sz,n);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 i=0;i<num;i++)
    if(buckets[i].size()&&
      buckets[i].back()>=arr[i]){
      id=i; 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][0]){
      id=max(0,i-1);break;}
  buckets[id].insert(lower_bound(all(buckets[id]),y),y);
  recalc(id);
  if(cnt==sz)
    cnt=0,recons();
  return gedans();
}

Compilation message (stderr)

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

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