Submission #854134

#	Time	Username	Problem	Language	Result	Execution time	Memory
854134		rxlfd314	Dancing Elephants (IOI11_elephants)	C++17	100 / 100	8982 ms	27228 KiB

elephants

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;
 
#define vt vector
#define size(x) (int(x.size()))
#define all(x) begin(x), end(x)
 
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)
 
#define chmax(a, b) a = a > (b) ? a : (b)
#define chmin(a, b) a = a < (b) ? a : (b)
 
static constexpr int mxN = 150005, B = 388;
static int N, L, pos[mxN];
static ari2 A[mxN];
static vt<array<int, 5>> blocks[B]; // position, index, next block, next index, value to add
static vt<ari2> endss;
 
void fix() {
  ROF(i, size(endss)-1, 1)
    if (endss[i] < endss[i-1])
      swap(endss[i], endss[i-1]);
}
 
static void upd(int b, bool added) {
  if (!size(blocks[b]))
    return;
  
  if (added)
    ROF(i, size(blocks[b])-1, 1)
      if (blocks[b][i][0] < blocks[b][i-1][0])
        swap(blocks[b][i], blocks[b][i-1]);
 
  endss.push_back({blocks[b].back()[0], b});
  fix();
 
  int j = size(blocks[b]) - 1;
  ROF(i, size(blocks[b])-1, 0) {
    if (blocks[b].back()[0] <= blocks[b][i][0] + L) {
      blocks[b][i][2] = blocks[b][i][3] = blocks[b][i][4] = B;
      continue;
    }
    while (blocks[b][j-1][0] > blocks[b][i][0] + L)
      j--;
    blocks[b][i] = {
      blocks[b][i][0], blocks[b][i][1], b, 
      blocks[b][j][2] == b ? blocks[b][j][3] : j, 
      blocks[b][j][2] == b ? blocks[b][j][4] + 1 : 1
    };
  }
}
 
static void recalc() {
  int cur = 0;
  FOR(i, 0, (N-1)/B)
    FOR(j, 0, size(blocks[i])-1)
      A[cur++] = {blocks[i][j][0], blocks[i][j][1]};
 
  FOR(i, 0, (N-1)/B) {
    blocks[i].clear();
    int n = min(N, (i+1)*B);
    FOR(j, i*B, n-1) {
      blocks[i].push_back({A[j][0], A[j][1], B, B, B});
      pos[A[j][1]] = i;
    }
  }
  
  endss.clear();
  ROF(b, (N-1)/B, 0)
    upd(b, false);
}
 
void init(int _N, int _L, int X[]) {
  N = _N, L = _L;
  FOR(i, 0, N-1)
    blocks[0].push_back({X[i], i, B, B, B});
  recalc();
}
 
static int it_cnt;
int update(int ind, int y) {
  int &p = pos[ind];
  FOR(i, 0, size(blocks[p])-1) {
    if (blocks[p][i][1] == ind) {
      if (i == size(blocks[p])-1) {
        endss.erase(find(all(endss), ari2{blocks[p][i][0], p}));
        if (i) {
          endss.push_back({blocks[p][i-1][0], p});
          fix();
        }
      }
      blocks[p].erase(begin(blocks[p]) + i);
      break;
    }
  }
 
  int it = lower_bound(all(endss), ari2{y, 0}) - begin(endss);
  it -= it == size(endss);
  int np = endss[it][1];
  endss.erase(begin(endss) + it);
  blocks[np].push_back({y, ind, B, B, B});
  if (size(blocks[p]) && p != np)
    endss.erase(find(all(endss), ari2{blocks[p].back()[0], p}));
 
  if (p < np) {
    upd(np, true);
    upd(p, false);
  } else if (p > np) {
    upd(p, false);
    upd(np, true);
  } else {
    upd(p, true);
  }
  p = np; // lol
 
  if (++it_cnt % B == 0)
    recalc();
 
  int cb = endss[0][1], ce = 0, ret = 0;
  while (cb < B) {
    if (blocks[cb][ce][2] != cb) {
      int it_r = lower_bound(all(endss), ari2{blocks[cb][ce][0]+L+1, 0}) - begin(endss);
      int r = it_r < size(endss) ? endss[it_r][1] : B;
      int rr = r == B ? 0 : lower_bound(all(blocks[r]), array<int, 5>{blocks[cb][ce][0]+L+1, 0, 0, 0, 0}) - begin(blocks[r]);
      blocks[cb][ce] = {blocks[cb][ce][0], blocks[cb][ce][1], r, rr, 1};
    }
    ret += blocks[cb][ce][4];
    int nb = blocks[cb][ce][2], ne = blocks[cb][ce][3];
    cb = nb, ce = ne;
  }
 
  return ret;
}

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