Submission #826148

#	Time	Username	Problem	Language	Result	Execution time	Memory
826148		KoD	Sequence (APIO23_sequence)	C++17	100 / 100	635 ms	43340 KiB

sequence

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

struct node {
  int min, max, sum;
  static node id() { return {0, 0, 0}; }
  static node one(int x) { return {std::min(x, 0), std::max(x, 0), x}; }
  node operator+(const node& n) const { return node(*this) += n; }
  node& operator+=(const node& n) {
    min = std::min(min, n.min + sum);
    max = std::max(max, n.max + sum);
    sum += n.sum;
    return *this;
  }
};

struct segment_tree {
  explicit segment_tree(int n, const node& x) : size(n), data(2 * n, x) {
    for (int i = n - 1; i > 0; --i) fetch(i);
  }

  void set(int i, const node& n) {
    i += size;
    data[i] = n;
    while (i >>= 1) fetch(i);
  }

  int sum(int l, int r) const {
    l += size, r += size;
    int ret = 0;
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1) ret += data[l++].sum;
      if (r & 1) ret += data[--r].sum;
    }
    return ret;
  }

  node fold(int l, int r) const {
    l += size, r += size;
    node ret_l = node::id(), ret_r = node::id();
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1) ret_l += data[l++];
      if (r & 1) ret_r = data[--r] + ret_r;
    }
    return ret_l + ret_r;
  }

 private:
  int size;
  vector<node> data;

  void fetch(int i) { data[i] = data[2 * i + 0] + data[2 * i + 1]; }
};

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;
  }
  for (int phase = 0; phase < 2; ++phase) {
    segment_tree seg(N, node::one(-1));
    for (int x = 0; x < N; ++x) {
      const auto& v = C[x];
      const int n = (int)v.size();
      for (const int i : v) seg.set(i, node::one(+1));
      if (n <= ret) continue;
      for (int i = 0, j = 0; i < n; ++i) {
        const auto [l0, r0, $0] = seg.fold(0, v[i]);
        while (j < n) {
          const int offset = seg.sum(0, v[j] + 1);
          const auto [l1, r1, $1] = seg.fold(v[j] + 1, N);
          if (std::max(l0, l1 + offset) > std::min(r0, r1 + offset)) break;
          j += 1;
        }
        ret = std::max(ret, j - i);
      }
    }
    std::reverse(C.begin(), C.end());
  }
  return ret;
}

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