Submission #1149652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149652		abczz	Dancing Elephants (IOI11_elephants)	C++20	50 / 100	3855 ms	12184 KiB

elephants

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include "elephants.h"
#include <iostream>
#include <map>
#include <queue>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <array>
#include <algorithm>
#define ll long long

using namespace std;

unordered_map <ll, ll> mp;
unordered_map <ll, array<ll, 3>> nx;
ll G[500][1000], gsz[500];
ll V[500], sz, cur;
array <ll, 2> lazy[400];
ll n, l, rtn, q = 150000, rtq, t, A[150000];
void init(int N, int L, int X[])
{
  n = N, l = L+1, rtn = sqrt(n), rtq = 10*sqrt(q), t = 0;
  mp.clear();
  for (int i=0; i<n; ++i) A[i] = X[i], ++mp[A[i]];
  ll s = 0;
  for (int i=0; i<n; ++i) {
    if (i != n-1 && A[i] == A[i+1]) continue;
    G[sz][gsz[sz]++] = A[i];
    if (s == 0) V[sz] = A[i];
    ++s;
    if (s == rtn) s = 0, ++sz;
  }
  if (gsz[sz]) ++sz;
}

ll tail() {
  ll u = sz-1;
  while (true) {
    if (gsz[u]) return G[u][gsz[u]-1];
    else --u;
  }
}

ll pv_it(ll z) {
  if (z == -1) return tail();
  while (z >= 0) {
    if (gsz[z]) return G[z][gsz[z]-1];
    else --z;
  }
  return -1;
}

ll nx_it(ll z) {
  while (z < sz) {
    if (gsz[z]) return G[z][0];
    else ++z;
  }
  return -1;
}

ll lb(ll x, bool b) {
  auto it = lower_bound(V, V+sz, x+1);
  if (it == V) return -1;
  it = prev(it);
  ll z = it-V;
  auto it2 = lower_bound(G[z], G[z]+gsz[z], x);
  if (it2 != G[z]+gsz[z]) {
    if (!b) return *it2;
    else {
      if (it2 != G[z]) return *prev(it2);
      else if (z >= 0) return pv_it(z-1);
      else return -1;
    }
  }
  else {
    if (!b) return nx_it(z+1);
    else {
      if (gsz[z]) return G[z][gsz[z]-1];
      else if (z >= 0) return pv_it(z-1);
      else return -1;
    }
  }
}

void ins(ll x) {
  auto it = lower_bound(V, V+sz, x+1);
  if (it == V) return;
  it = prev(it);
  ll z = it-V;
  G[z][gsz[z]++] = x;
  for (int i=0; i<gsz[z]; ++i) {
    if (G[z][i] > G[z][gsz[z]-1]) swap(G[z][i], G[z][gsz[z]-1]);
  }
}

void rmv(ll x) {
  auto it = lower_bound(V, V+sz, x+1);
  if (it == V) return;
  it = prev(it);
  ll z = it-V;
  for (int i=0; i+1<gsz[z]; ++i) {
    if (G[z][i] == x) swap(G[z][i], G[z][i+1]);
  }
  --gsz[z];
}

void update_nx(ll z, ll st, ll tar) {
  ll id = gsz[z]-1, z2 = z, id2 = id;
  while (true) {
    //it = prev(it);
    while (id < 0) {
      if (z == 0) return;
      if (st == -1) --z, id = gsz[z]-1;
      else return;
    }
    while (true) {
      while (id2 < 0) {
        --z2, id2 = (ll)gsz[z2]-1;
      }
      if (G[z][id]+l <= G[z2][id2]) cur = G[z2][id2], --id2;
      else break;
    }
    if (cur == -1 || G[z][id]+l > cur) {
      if (G[z][id]+l > tail()) nx[G[z][id]] = {-1, 0, t};
    }
    else {
      auto u = nx[cur];
      if (z == sz-1 || cur < V[z+1]) {
        nx[G[z][id]] = {u[0], u[1]+1, t};
        //cout << "*" << G[z][id] << " " << tar << " " << nx[G[z][id]][0] << " " << nx[G[z][id]][1] << endl;
      }
      else if (st == -1 || G[z][id] >= tar) {
        nx[G[z][id]] = {cur, 1, t};
        //cout << "*" << G[z][id] << " " << tar << " " << nx[G[z][id]][0] << " " << nx[G[z][id]][1] << endl;
      }
    }
    --id;
  }
}

void reinit() {
  cur = -1;
  vector <ll> U;
  for (int i=0; i<sz; ++i) {
    for (int j=0; j<gsz[i]; ++j) U.push_back(G[i][j]);
  }
  for (int i=0; i<rtn+5; ++i) {
    lazy[i] = {-1, -1};
    gsz[i] = 0;
  }
  nx.clear();
  sz = 0;
  ll s = 0;
  for (auto x : U) {
    G[sz][gsz[sz]++] = x;
    if (s == 0) V[sz] = x;
    ++s;
    if (s == rtn) s = 0, ++sz;
  }
  if (gsz[sz]) ++sz;
  V[0] = 0;
  ll z = sz-1;
  update_nx(z, -1, -1);
}

void add(ll x) {
  //cout << "+" << x << endl;
  cur = x;
  ++mp[x];
  ins(x);
  ll pv;
  ll it = lb(x+l, 0);
  if (it == -1) nx[x] = {-1, 0, t};
  else nx[x] = {it, 1, t};
  //cout << "*" << x << " " << nx[x][0] <<endl;
  auto vt = lower_bound(V, V+sz, x-l+1);
  if (vt == V) return;
  vt = prev(vt);
  ll z = vt-V;
  ll it2 = lb(x, 1);
  if (it2 == -1) return;
  pv = it2;
  update_nx(z, 0, pv-l+1);
  --z;
  while (z >= 0 && V[z] > pv-l) {
    //cout << z << "?" << x << endl;
    lazy[z] = {x, t};
    --z;
  }
  if (z >= 0) {
    cur = x;
    update_nx(z, 0, pv-l+1);
  }
}

void remove(ll x) {
  //cout << "-" << x << endl;
  mp.erase(x);
  nx.erase(x);
  rmv(x);
  ll pv, nt;
  ll it = lb(x, 0);
  cur = nt = it;
  it = lb(x, 1);
  if (it == -1) return;
  pv = it;
  auto vt = lower_bound(V, V+sz, x-l+1);
  if (vt == V) return;
  vt = prev(vt);
  ll z = vt-V;
  update_nx(z, 0, pv-l+1);
  --z;
  while (z >= 0 && V[z] > pv-l) {
    //cout << z << "?" << x << endl;
    lazy[z] = {nt, t};
    --z;
  }
  if (z >= 0) {
    cur = nt;
    update_nx(z, 0, pv-l+1);
  }
}

ll query() {
  ll f = 0, z = 0, u;
  while (z < sz) {
    if (gsz[z]) {
      u = G[z][0];
      break;
    }
    else ++z;
  }
  while (true) {
    while (z != sz-1 && V[z+1] <= u) ++z;
    //cout << u << "->" << nx[u][0] << " " << lazy[z][0] << endl;
    if (nx[u][2] >= lazy[z][1]) {
      f += nx[u][1];
      if (nx[u][0] == -1) break;
      u = nx[u][0];
    }
    else {
      if (lazy[z][0] == -1) break;
      u = lazy[z][0];
      ++f;
    }
  }
  return f+1;
}

int update(int i, int y)
{
  if (t % (2*rtq) == 0) {
    ++t;
    reinit();
  }
  else ++t;
  if (mp[A[i]] == 1) remove(A[i]);
  else --mp[A[i]];
  ++t;
  if (!mp.count(y)) add(y);
  else ++mp[y];
  A[i] = y;
  return query();
}

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