Submission #1149611

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149611		abczz	Dancing Elephants (IOI11_elephants)	C++20	97 / 100	9088 ms	23232 KiB

elephants

#include "elephants.h"
#include <iostream>
#include <map>
#include <queue>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <algorithm>
#define ll long long

using namespace std;

unordered_map <ll, ll> mp;
unordered_map <ll, array<ll, 3>> nx;
vector <ll> G[500];
ll V[500], sz, cur;
queue <ll> Q;
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]];
  vector <ll> U;
  ll s = 0;
  for (int i=0; i<n; ++i) {
    if (i != n-1 && A[i] == A[i+1]) continue;
    G[sz].push_back(A[i]);
    if (s == 0) V[sz] = A[i];
    ++s;
    if (s == rtn) s = 0, ++sz;
  }
  if (!G[sz].empty()) ++sz;
}


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

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

ll nx_it(ll z) {
  while (z < sz) {
    if (!G[z].empty()) 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].begin(), G[z].end(), x);
  if (it2 != G[z].end()) {
    if (!b) return *it2;
    else {
      if (it2 != G[z].begin()) 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 (!G[z].empty()) return G[z].back();
      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].push_back(x);
  for (int i=0; i<G[z].size(); ++i) {
    if (G[z][i] > G[z].back()) swap(G[z][i], G[z][G[z].size()-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<G[z].size(); ++i) {
    if (G[z][i] == x) swap(G[z][i], G[z][i+1]);
  }
  G[z].pop_back();
}

void update_nx(ll z, ll st, ll tar) {
  ll id = G[z].size()-1;
  while (true) {
    //it = prev(it);
    while (id < 0) {
      if (z == 0) return;
      if (st == -1) --z, id = (ll)G[z].size()-1;
      else return;
    }
    while (!Q.empty()) {
      if (G[z][id]+l <= Q.front()) {
        cur = Q.front();
        Q.pop();
      }
      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;
      }
    }
    Q.push(G[z][id]);
    --id;
  }
}

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

void add(ll x) {
  //cout << "+" << x << endl;
  while (!Q.empty()) Q.pop();
  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, (z == sz-1 ? (ll)1e18 : V[z+1]), pv-l+1);
  --z;
  while (z >= 0 && V[z] > pv-l) {
    //cout << z << "?" << x << endl;
    lazy[z] = {x, t};
    --z;
  }
  if (z >= 0) {
    while (!Q.empty()) Q.pop();
    cur = x;
    update_nx(z, (z == sz-1 ? (ll)1e18 : V[z+1]), pv-l+1);
  }
}

void remove(ll x) {
  //cout << "-" << x << endl;
  while (!Q.empty()) Q.pop();
  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, (z == sz-1 ? (ll)1e18 : V[z+1]), pv-l+1);
  --z;
  while (z >= 0 && V[z] > pv-l) {
    //cout << z << "?" << x << endl;
    lazy[z] = {nt, t};
    --z;
  }
  if (z >= 0) {
    while (!Q.empty()) Q.pop();
    cur = nt;
    update_nx(z, (z == sz-1 ? (ll)1e18 : V[z+1]), pv-l+1);
  }
}

ll query() {
  ll f = 0;
  //cout << "start" << endl;
  ll z = 0, u = nx_it(0);
  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)
{
  /*for (int i=0; i<sz; ++i) {
    for (auto u : G[i]) cout << u << "#";
    cout << endl;
  }*/
  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;
  /*for (int i=0; i<sz; ++i) {
    for (auto u : G[i]) cout << u << "#";
    cout << endl;
  }*/
  return query();
}

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