제출 #826028

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
826028		KoD	서열 (APIO23_sequence)	C++17	11 / 100	2075 ms	48384 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);
    // }
    vector<int> a = initial;
    for (int x = 0; x < N; ++x) {
      const auto& v = C[x];
      const int n = (int)v.size();
      vector<int> cnt(N + 1);
      for (const int i : v) cnt[i + 1] += 1;
      for (int i = 0; i < N; ++i) cnt[i + 1] += cnt[i];
      vector<int> lmin = a, rmin = a, lmax = a, rmax = a;
      for (int i = 0; i < N; ++i) lmin[i + 1] = std::min(lmin[i + 1], lmin[i]);
      for (int i = 0; i < N; ++i) lmax[i + 1] = std::max(lmax[i + 1], lmax[i]);
      for (int i = N - 1; i >= 0; --i) rmin[i] = std::min(rmin[i], rmin[i + 1]);
      for (int i = N - 1; i >= 0; --i) rmax[i] = std::max(rmax[i], rmax[i + 1]);
      for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j <= N; ++j) {
          if (std::max(lmin[i], rmin[j]) <= std::min(lmax[i], rmax[j])) {
            ret = std::max(ret, cnt[j] - cnt[i]);
          }
        }
      }
      for (const int i : v) {
        for (int j = i + 1; j <= N; ++j) a[j] += 2;
      }
    }
    std::reverse(C.begin(), C.end());
  }
  return ret;
}

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:114:17: warning: unused variable 'n' [-Wunused-variable]
  114 |       const int n = (int)v.size();
      |                 ^

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