Submission #365356

#	Time	Username	Problem	Language	Result	Execution time	Memory
365356		WLZ	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	5011 ms	14220 KiB

elephants

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

int n, l, k;
vector<int> x;
vector< vector<int> > buckets, cnt, last;

void rebuild(int i) {
  cnt[i].resize((int) buckets[i].size());
  last[i].resize((int) buckets[i].size());  
  int ptr = (int) buckets[i].size();
  for (int j = (int) buckets[i].size() - 1; j >= 0; j--) {
    while (ptr > j && buckets[i][ptr - 1] > buckets[i][j] + l) ptr--;
    if (buckets[i].back() - l <= buckets[i][j]) cnt[i][j] = 1, last[i][j] = buckets[i][j] + l;
    else cnt[i][j] = cnt[i][ptr] + 1, last[i][j] = last[i][ptr];
  }
}

void init(int N, int L, int X[]) {
  n = N, l = L, k = sqrt(n);
  for (int i = 0; i < n; i++) x.push_back(X[i]);
  buckets.push_back({});
  for (int i = 0; i < n; i++) {
    if ((int) buckets.back().size() == k) buckets.push_back({});
    buckets.back().push_back(x[i]);
  }
  cnt.resize((int) buckets.size()); last.resize((int) buckets.size());
  for (int i = 0; i < (int) buckets.size(); i++) rebuild(i);
}

int calc() {
  int prev = -1, ans = 0;
  for (int i = 0; i < (int) buckets.size(); i++) {
    auto it = upper_bound(buckets[i].begin(), buckets[i].end(), prev);
    if (it == buckets[i].end()) continue;
    int j = it - buckets[i].begin();
    ans += cnt[i][j];
    prev = last[i][j];
  }
  return ans;
}

int cur = 0;

void rebuild() {
  vector<int> tmp;
  for (int i = 0; i < (int) buckets.size(); i++) {
    for (int j = 0; j < (int) buckets[i].size(); j++) {
      tmp.push_back(buckets[i][j]);
    }
    buckets[i].clear();
  }
  int idx = 0;
  for (int i = 0; i < (int) tmp.size(); i++) {
    if (buckets[idx].size() == k) idx++;
    buckets[idx].push_back(tmp[i]);
  }
  for (int i = 0; i < (int) buckets.size(); i++) rebuild(i);
}

int update(int i, int y) {
  if (++cur == (n + k - 1) / k) {
    rebuild();
    cur = 0;
  }
  int idx = 0;
  while (buckets[idx].back() < x[i]) idx++;
  for (auto it = buckets[idx].begin(); ; it++) {
    if (*it == x[i]) {
      buckets[idx].erase(it);
      break;
    }
  }
  if (buckets[idx].empty()) rebuild();
  else rebuild(idx);
  x[i] = y;
  idx = 0;
  while (idx < (int) buckets.size() && buckets[idx].back() < x[i]) idx++;
  if (idx == (int) buckets.size()) idx--;
  bool added = false;
  for (auto it = buckets[idx].begin(); it != buckets[idx].end(); it++) {
    if (*it > x[i]) {
      buckets[idx].insert(it, x[i]);
      added = true;
      break;
    }
  }
  if (!added) buckets[idx].push_back(x[i]);
  rebuild(idx);
  return calc();
}

Compilation message (stderr)

elephants.cpp: In function 'void rebuild()':
elephants.cpp:56:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |     if (buckets[idx].size() == k) idx++;
      |         ~~~~~~~~~~~~~~~~~~~~^~~~

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