Submission #1149919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149919		abczz	Dancing Elephants (IOI11_elephants)	C++20	100 / 100	4118 ms	19984 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;
ll G[500][5000], gsz[500];
array <ll, 2> nx[500][5000];
ll V[500], sz, cur;
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 = 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;
}

void update_nx(ll z) {
  ll id = gsz[z]-1, id2 = id;
  while (true) {
    if (id < 0) return;
    while (true) {
      if (id2 > 0 && G[z][id]+l <= G[z][id2-1]) --id2;
      else break;
    }
    if (G[z][id]+l > G[z][id2]) nx[z][id] = {id, 0};
    else nx[z][id] = {nx[z][id2][0], nx[z][id2][1]+1};
    //cout << G[z][id] << " " << G[z][id2] << " " << nx[z][id][0] << " " << nx[z][id][1] << endl;
    --id;
  }
}

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]);
  }
  update_nx(z);
}

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];
  update_nx(z);
}

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) gsz[i] = 0;
  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;
  for (int i=0; i<sz; ++i) update_nx(i);
}

void add(ll x) {
  //cout << "+" << x << endl;
  ++mp[x];
  ins(x);
}

void remove(ll x) {
  //cout << "-" << x << endl;
  mp.erase(x);
  rmv(x);
}

ll query() {
  ll f = 0, u = -1e18;
  for (int i=0; i<sz; ++i) {
    if (!gsz[i] || u+l > G[i][gsz[i]-1]) continue;
    for (int j=0; j<gsz[i]; ++j) {
      if (u+l <= G[i][j]) {
        f += nx[i][j][1]+1;
        u = G[i][nx[i][j][0]];
        break;
      }
    }
    //cout << u << " " << f << endl;
  }
  //cout << endl;
  return f;
}

int update(int i, int y)
{
  if (t % rtq == 0) reinit();
  ++t;
  if (mp[A[i]] == 1) remove(A[i]);
  else --mp[A[i]];
  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: 47 / 47
• Subtask 5: 3 / 3