Submission #1169626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169626		blackslex	코끼리 (Dancing Elephants) (IOI11_elephants)	C++20	97 / 100	9014 ms	19348 KiB

elephants

#include "elephants.h"
#include<bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

const int MxN = 1.5e5 + 5, MxK = 400;
int n, l, x[MxN], cnt, z[MxN];
vector<int> v[MxK];
vector<pii> dp[MxK];
multiset<int> ms[MxK];

void upd (int idx) {
  v[idx].clear();
  for (auto &e: ms[idx]) v[idx].emplace_back(e);
  if (v[idx].empty()) return;
  // cerr << "UPD " << idx << '\n';
  // for (auto &e: v[idx]) cerr << e << ' '; cerr << '\n';
  int csz = v[idx].size();
  dp[idx].resize(csz);
  deque<int> dq;
  for (int i = csz - 1; i >= 0; i--) {
    while (dq.size() > 1 && v[idx][dq.end()[-2]] > v[idx][i] + l) dq.pop_back();
    if (dq.empty() || v[idx][i] + l >= v[idx][dq.back()]) {
      dp[idx][i] = {v[idx][i] + l, 1};
    } else {
      dp[idx][i] = {dp[idx][dq.back()].first, dp[idx][dq.back()].second + 1};
    }
    dq.emplace_front(i);
  }
  // for (int i = 0; i < csz; i++) {
  //   cerr << "[" << dp[idx][i].first << ' ' << dp[idx][i].second << "]\n";
  // }
}

void build() {
  vector<pii> c;
  for (int i = 0; i < n; i++) {
    c.emplace_back(x[i], i);
  }
  sort(c.begin(), c.end());
  for (int i = 0; i < MxK; i++) ms[i].clear();
  for (int i = 0; i < n; i++) {
    auto [x, y] = c[i];
    z[y] = i / MxK;
    ms[z[y]].emplace(x);
  }
  for (int i = 0; i < MxK; i++) {
    upd(i);
  }
}

int qr() {
  // cerr << "QR\n";
  int lst = -1, res = 0;
  for (int i = 0; i < MxK; i++) {
    int csz = v[i].size();
    if (v[i].empty() || lst >= v[i][csz - 1]) continue;
    int idx = upper_bound(v[i].begin(), v[i].end(), lst) - v[i].begin();
    // cerr << "OO " << i << '\n';
    // for (auto &e: v[i]) cerr << e << ' '; cerr << '\n';
    lst = dp[i][idx].first;
    res += dp[i][idx].second;
  }
  // cerr << "ENDQR\n";
  return res;
}

void init(int N, int L, int X[]){
  n = N; l = L;
  for (int i = 0; i < n; i++) x[i] = X[i];
  build();
}

int update(int i, int y){
  if ((++cnt) % 987 == 0) {
    x[i] = y;
    build();
    return qr();
  }
  int b = z[i];
  ms[b].erase(ms[b].find(x[i]));
  // cerr << "WW " << i << ' ' << z[i] << ' ' << x[i] << ' ' << y << '\n';
  x[i] = y;
  upd(b);
  for (int j = 0; j < MxK; j++) {
    int csz = v[j].size();
    if (j == MxK - 1 || (!v[j].empty() && x[i] <= v[j][csz - 1])) {
      ms[j].emplace(x[i]);
      z[i] = j;
      upd(j);
      break;
    }
  }
  return qr();
}

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