제출 #726099

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

elephants

#include <bits/stdc++.h>
#include "elephants.h"

using namespace std;

const int kN = 1e5 + 5e4;
const int bucketSize = 1e3;
const int kBuckets = 150;
int n, len, a[kN], bucket[kN], indexInBucket[kN];
int updates, auxSize, auxIndices[kN];

class bucket_t {
  private:
    int N, indices[2 * bucketSize];
    int req[2 * bucketSize], maxReach[2 * bucketSize];

  public:
    void reset() {
      N = 0;
    }

    bool isEmpty() {
      return N == 0;
    }

    int getSize() {
      return N;
    }

    int last() {
      return a[indices[N - 1]];
    }

    void add(int index) {
      indices[N++] = index;
    }

    void addAll() {
      for (int i = 0; i < N; ++i) {
        auxIndices[auxSize++] = indices[i];
      }
    }

    int jumps(int index) {
      return req[index];
    }

    int furthest(int index) {
      return maxReach[index];
    }

    void build() {
      int r = N - 1;

      for (int l = N - 1; l >= 0; --l) {
        while (a[indices[r]] - a[indices[l]] > len) {
          r -= 1;
        }

        if (r == N - 1) {
          req[l] = 1;
          maxReach[l] = a[indices[l]] + len;
        } else {
          req[l] = req[r + 1] + 1;
          maxReach[l] = maxReach[r + 1];
        }
      }
    }

    void rem(int pos) {
      for (int i = pos; i < N - 1; ++i) {
        indices[i] = indices[i + 1];
        indexInBucket[indices[i]] = i;
      }

      N -= 1;

      build();
    }

    void ins(int index) {
      int ptr = N - 1;

      while (ptr >= 0 && a[index] < a[indices[ptr]]) {
        ptr -= 1;
      }

      for (int i = N; i > ptr + 1; --i) {
        indices[i] = indices[i - 1];
        indexInBucket[indices[i]] = i;
      }

      indices[ptr + 1] = index;
      indexInBucket[index] = ptr + 1;

      N += 1;

      build();
    }

    int upperBound(int x) {
      int l = -1, r = N;

      while (r - l > 1) {
        int mid = (l + r) / 2;

        if (mid != -1 && (mid == N || x < a[indices[mid]])) {
          r = mid;
        } else {
          l = mid;
        }
      }

      return r;
    }
} buckets[kBuckets];

void init(int N, int L, int X[]) {
  n = N;
  len = L;

  for (int i = 0; i <= (n - 1) / bucketSize; ++i) {
    buckets[i].reset();
  }

  for (int i = 0; i < n; ++i) {
    a[i] = X[i];
    bucket[i] = i / bucketSize;
    indexInBucket[i] = i % bucketSize;
    buckets[i / bucketSize].add(i);
  }

  for (int i = 0; i <= (n - 1) / bucketSize; ++i) {
    buckets[i].build();
  }
}

void rebuild() {
  auxSize = 0;

  for (int i = 0; i <= (n - 1) / bucketSize; ++i) {
    buckets[i].addAll();
    buckets[i].reset();
  }

  for (int i = 0; i < n; ++i) {
    bucket[auxIndices[i]] = i / bucketSize;
    indexInBucket[auxIndices[i]] = i % bucketSize;
    buckets[i / bucketSize].add(auxIndices[i]);
  }

  for (int i = 0; i <= (n - 1) / bucketSize; ++i) {
    buckets[i].build();
  }
}

int query() {
  int res = 0;

  int reach = -1;

  for (int i = 0; i <= (n - 1) / bucketSize; ++i) {
    if (!buckets[i].isEmpty() && reach < buckets[i].last()) {
      int index = buckets[i].upperBound(reach);
      res += buckets[i].jumps(index);
      reach = buckets[i].furthest(index);
    }
  }

  return res;
}

int update(int index, int x) {
  buckets[bucket[index]].rem(indexInBucket[index]);

  a[index] = x;
  bucket[index] = -1;

  for (int i = 0; i <= (n - 1) / bucketSize && bucket[index] == -1; ++i) {
    if (!buckets[i].isEmpty() && x <= buckets[i].last()) {
      bucket[index] = i;
    }
  }

  if (bucket[index] == -1) {
    bucket[index] = (n - 1) / bucketSize;
  }

  buckets[bucket[index]].ins(index);

  updates += 1;

  if (updates == bucketSize) {
    rebuild();
    updates = 0;
  }

  return query();
}

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