제출 #192442

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

elephants

#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;

#define b_size (400)

int n, l, m;
int x[150010], v[150010];
int bnum;
int ucnt;

struct Bucket{
  int sz;
  int x[2 * b_size + 1];
  int num[2 * b_size + 1];
  int bound[2 * b_size + 1];
  void calc(){
		int t = sz;
    for(int i = sz - 1; i >= 0; i--){
      while(t > 0 && x[t - 1] > x[i] + l) t--;
			if(t == sz) num[i] = 1, bound[i] = x[i] + l;
      else num[i] = num[t] + 1, bound[i] = bound[t];
    }
  }
  void ins(int y){
    int p = (int)(upper_bound(x, x + sz, y) - x);
    sz++;
    for(int i = sz - 1; i > p; i--) x[i] = x[i - 1];
    x[p] = y;
    calc();
  }
  void del(int y){
    int p = (int)(lower_bound(x, x + sz, y) - x);
    sz--;
    for(int i = p; i < sz; i++) x[i] = x[i + 1];
    calc();
  }

}b[b_size + 1];

void init(int n, int l, int x[]){
  ::n = n;
  ::l = l;
  for(int i = 0; i < n; i++) ::x[i] = x[i];
	for(int i = 0; i < n; i += b_size){
    for(int j = i; j < n && j < i + b_size; j++){
      b[bnum].x[b[bnum].sz++] = x[j];
    }
    b[bnum++].calc();
  }
}

void rebucket(){
  int cnt = 0;
  for(int i = 0; i < bnum; i++){
    for(int j = 0; j < b[i].sz; j++){
      v[cnt++] = b[i].x[j];
    }
  }
  bnum = 0;
  for(int i = 0; i < n; i += b_size){
    b[bnum].sz = 0;
    for(int j = i; j < n && j < i + b_size; j++){
      b[bnum].x[b[bnum].sz++] = v[j];
    }
    b[bnum++].calc();
  }
}

int update(int i, int y){
  int pv = x[i];
  x[i] = y;
  for(int i = 0; i < bnum; i++){
    if(b[i].sz == 0) continue;
    if(b[i].x[0] <= pv && b[i].x[b[i].sz - 1] >= pv){b[i].del(pv); break;}
  }
  for(int i = 0; i < bnum; i++){
    if(b[i].sz == 0) continue;
    if((i == 0 || b[i].x[0] <= y) && (i == bnum - 1 || b[i + 1].x[0] > y)){b[i].ins(y); break;}
  }
  int ret = 0;
  int lst = -1;
  for(int i = 0; i < bnum; i++){
    if(lst >= b[i].x[b[i].sz - 1]) continue;
    if(lst < b[i].x[0]){ret += b[i].num[0]; lst = b[i].bound[0];}
    else{
      int p = (int)(upper_bound(b[i].x, b[i].x + b[i].sz, lst) - b[i].x);
      ret += b[i].num[p]; lst = b[i].bound[p];
    }
  }
  ucnt++;
  if(ucnt % (b_size - 5) == 0) rebucket();
  return ret;
}

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