제출 #825885

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
825885		KoD	서열 (APIO23_sequence)	C++17	32 / 100	780 ms	47156 KiB

sequence

#include "sequence.h"
#include <algorithm>
#include <utility>
#include <vector>
using std::pair;
using std::vector;

constexpr int inf = 1 << 30;

struct segment_tree {
  explicit segment_tree(const vector<int>& v) {
    const int n = (int)v.size();
    for (logn = 0; (1 << logn) < n; ++logn)
      ;
    size = 1 << logn;
    min.resize(2 * size);
    max.resize(2 * size);
    add.resize(size);
    for (int i = 0; i < n; ++i) min[i + size] = max[i + size] = v[i];
    for (int i = size - 1; i > 0; --i) fetch(i);
  }

  void range_add(int l, int r, int x) {
    l += size, r += size;
    push(l), push(r);
    for (int s = l, t = r; s < t; s >>= 1, t >>= 1) {
      if (s & 1) apply(s++, x);
      if (t & 1) apply(--t, x);
    }
    pull(l), pull(r);
  }

  pair<int, int> fold(int l, int r) {
    l += size, r += size;
    push(l), push(r);
    int s = +inf, t = -inf;
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1) {
        s = std::min(s, min[l]);
        t = std::max(t, max[l]);
        l += 1;
      }
      if (r & 1) {
        r -= 1;
        s = std::min(s, min[r]);
        t = std::max(t, max[r]);
      }
    }
    return {s, t};
  }

 private:
  int size, logn;
  vector<int> min, max, add;

  void apply(int i, int x) {
    min[i] += x;
    max[i] += x;
    if (i < size) add[i] += x;
  }
  void flush(int i) {
    apply(2 * i + 0, add[i]);
    apply(2 * i + 1, add[i]);
    add[i] = 0;
  }
  void fetch(int i) {
    min[i] = std::min(min[2 * i + 0], min[2 * i + 1]);
    max[i] = std::max(max[2 * i + 0], max[2 * i + 1]);
  }

  void push(int i) {
    const int rz = __builtin_ctz(i);
    for (int k = logn; k > rz; --k) flush(i >> k);
  }
  void pull(int i) {
    i >>= __builtin_ctz(i);
    while (i >>= 1) fetch(i);
  }
};

int sequence(int N, vector<int> A) {
  vector<vector<int>> C(N);
  for (int i = 0; i < N; ++i) {
    A[i] -= 1;
    C[A[i]].push_back(i);
  }
  int ret = 0;
  for (int i = 0, j = 0; i < N; ++i) {
    const int c = (int)C[i].size();
    if (j <= N / 2 && N / 2 < j + c) ret = std::max(ret, c);
    j += c;
  }
  vector<int> initial(N + 1);
  for (int i = 0; i <= N; ++i) initial[i] = -i;
  for (int phase = 0; phase < 2; ++phase) {
    segment_tree seg(initial);
    for (int x = 0; x < N; ++x) {
      const auto& v = C[x];
      const int n = (int)v.size();
      for (int i = 0, j = 0; i < n; i = j) {
        const auto [l0, r0] = seg.fold(0, v[i] + 1);
        while (j < n) {
          const auto [l1, r1] = seg.fold(v[j] + 1, N + 1);
          if (std::max(l0, l1) > std::min(r0, r1)) break;
          j += 1;
        }
        ret = std::max(ret, j - i);
        if (i == j) j += 1;
      }
      for (const int i : v) seg.range_add(i + 1, N + 1, 2);
    }
    std::reverse(C.begin(), C.end());
  }
  return ret;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 17
• Subtask 3: 7 / 7
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18