제출 #1149485

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149485		abczz	코끼리 (Dancing Elephants) (IOI11_elephants)	C++20	26 / 100	9093 ms	2888 KiB

elephants

#include "elephants.h"
#include <iostream>
#include <map>
#include <deque>
#include <vector>
#include <cmath>
#define ll long long

using namespace std;

map <ll, ll> mp;
map <ll, array<ll, 3>> nx;
vector <ll> V;
deque <ll> dq;
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 = sqrt(q), t = 0;
  mp.clear();
  for (int i=0; i<n; ++i) A[i] = X[i], ++mp[A[i]];
}

void update_nx(ll z, ll st, ll tar) {
  auto it = mp.end();
  if (st != -1) it = mp.lower_bound(st);
  while (it != mp.begin()) {
    it = prev(it);
    while (z >= 0 && it->first < V[z]) {
      if (st == -1) --z;
      else break;
    }
    while (dq.size() > 1) {
      auto u = dq.front();
      dq.pop_front();
      if (it->first+l <= dq.front()) continue;
      else {
        dq.push_front(u);
        break;
      }
    }
    if (dq.empty() || it->first+l > dq.front()) {
      if (it->first+l > prev(mp.end())->first) nx[it->first] = {-1, 0, t};
    }
    else {
      auto u = nx[dq.front()];
      if (z == V.size()-1 || dq.front() < V[z+1]) {
        nx[it->first] = {u[0], u[1]+1, t};
        //cout << dq.front() << endl;
        //cout << "*" << it->first << " " << tar << " " << nx[it->first][0] << " " << nx[it->first][1] << endl;
      }
      else if (st == -1 || it->first >= tar) {
        nx[it->first] = {dq.front(), 1, t};
        //cout << "*" << it->first << " " << tar << " " << nx[it->first][0] << " " << nx[it->first][1] << endl;
      }
    }
    dq.push_back(it->first);
  }
}

void reinit() {
  while (!dq.empty()) dq.pop_back();
  for (int i=0; i<rtn; ++i) lazy[i] = {-1, -1};
  V.clear();
  nx.clear();
  ll s = 0;
  for (auto [x, y] : mp) {
    if (s == 0) V.push_back(x);
    ++s;
    if (s == rtn) s = 0;
  }
  V[0] = 0;
  ll z = V.size()-1;
  update_nx(z, -1, -1);
  /*for (auto u : V) cout << u << "#";
  cout << endl;*/
}

void add(ll x) {
  //cout << "+" << x << endl;
  while (!dq.empty()) dq.pop_back();
  dq.push_front(x);
  ++mp[x];
  ll pv;
  auto it = mp.lower_bound(x+l);
  if (it == mp.end()) nx[x] = {-1, 0, t};
  else nx[x] = {it->first, 1, t};
  //cout << "*" << x << " " << nx[x][0] <<endl;
  auto vt = lower_bound(V.begin(), V.end(), x-l+1);
  if (vt == V.begin()) return;
  vt = prev(vt);
  ll z = vt-V.begin();
  auto it2 = mp.lower_bound(x);
  if (it2 == mp.begin()) return;
  pv = prev(it2)->first;
  update_nx(z, (z == V.size()-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 (!dq.empty()) dq.pop_back();
    dq.push_front(x);
    update_nx(z, (z == V.size()-1 ? (ll)1e18 : V[z+1]), pv-l+1);
  }
}

void remove(ll x) {
  //cout << "-" << x << endl;
  while (!dq.empty()) dq.pop_back();
  mp.erase(x);
  nx.erase(x);
  ll pv, nt;
  auto it = mp.lower_bound(x);
  if (it == mp.end()) nt = -1;
  else {
    nt = it->first;
    dq.push_front(nt);
  }
  if (it == mp.begin()) return;
  pv = prev(it)->first;
  auto vt = lower_bound(V.begin(), V.end(), x-l+1);
  if (vt == V.begin()) return;
  vt = prev(vt);
  ll z = vt-V.begin();
  update_nx(z, (z == V.size()-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 (!dq.empty()) dq.pop_back();
    dq.push_front(nt);
    update_nx(z, (z == V.size()-1 ? (ll)1e18 : V[z+1]), pv-l+1);
  }
}

ll query() {
  ll f = 0;
  auto it = mp.begin();
  while (it != mp.end()) {
    auto vt = lower_bound(V.begin(), V.end(), it->first+1);
    vt = prev(vt);
    ll z = vt-V.begin();
    //cout << it->first << " " << nx[it->first][1] << " " << lazy[z][0] << endl;
    if (nx[it->first][2] >= lazy[z][1]) {
      f += nx[it->first][1];
      if (nx[it->first][0] == -1) break;
      it = mp.find(nx[it->first][0]);
    }
    else {
      if (lazy[z][0] == -1) break;
      it = mp.find(lazy[z][0]);
      ++f;
    }
  }
  return f+1;
}

int update(int i, int y)
{
  if (t % rtq == 0) {
    ++t;
    reinit();
  }
  else ++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: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3