Submission #418743

#	Time	Username	Problem	Language	Result	Execution time	Memory
418743		Hegdahl	Dancing Elephants (IOI11_elephants)	C++17	97 / 100	9025 ms	6608 KiB

elephants

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "elephants.h"
#define ar array
using namespace std;

const int mxN = 15e4;
int n, l, R, a[mxN], idxs[mxN], where[mxN];

struct Chunk {
  int size;
  vector<int> xs;
  vector<ar<int, 2>> dp;

  Chunk(vector<int> &&_xs) : size((int)_xs.size()), xs(move(_xs)) {
    recalc();
  }

  void recalc() {
    dp.resize(size);
    for (int i = size-1; i >= 0; --i) {
      int j = lower_bound(xs.begin(), xs.end(), xs[i]+l) - xs.begin();
      if (j == size) dp[i] = {1, xs[i]+l};
      else dp[i] = {dp[j][0]+1, dp[j][1]};
    }
  }

  void insert(int x) {
    ++size;
    auto it = upper_bound(xs.begin(), xs.end(), x);
    xs.insert(it, x);
    recalc();
  }

  void erase(int x) {
    --size;
    auto it = lower_bound(xs.begin(), xs.end(), x);
    assert(it != xs.end());
    xs.erase(it);
    recalc();
  }

  ar<int, 2> qry(int x) {
    int j = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
    if (j == size) return {0, x};
    return dp[j];
  }
};

vector<Chunk> chunks;

void recalc() {
  iota(idxs, idxs+n, 0);
  sort(idxs, idxs+n, [&](int i, int j){ return a[i] < a[j]; });

  chunks.clear();
  for (int i0 = 0; i0 < n; i0 += R) {
    vector<int> xs;
    for (int i = i0; i < min(i0+R, n); ++i) {
      xs.push_back(a[idxs[i]]);
      where[idxs[i]] = (int)chunks.size();
    }
    chunks.emplace_back(move(xs));
  }
}

void init(int N, int L, int X[]) {
  n = N, l = L+1;
  for (int i = 0; i < n; ++i)
    a[i] = X[i];

  R = sqrt(N);

  recalc();
}

int solve() {
  int x = -1e9-10, ans = 0;

  for (int c = 0; c < (int)chunks.size(); ++c) {
    auto [used, new_x] = chunks[c].qry(x);
    ans += used;
    x = new_x;
  }

  return ans;
}

int update(int i, int y) {
  static int update_cnt = 0;
  if (++update_cnt%R == 0) {
    a[i] = y;
    recalc();
  } else {
    int c = where[i];
    chunks[c].erase(a[i]);

    a[i] = y;

    for (c = 1; c < (int)chunks.size(); ++c)
      if (chunks[c].size && chunks[c].xs[0] > a[i]) break;
    --c;
    chunks[c].insert(a[i]);
    where[i] = c;
  }

  return solve();
}

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