제출 #1282943

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282943		rxlfd314	Sequence (APIO23_sequence)	C++17	100 / 100	542 ms	50676 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

struct Node {
  int sum, pmax, pmin;
  Node operator+(const Node &x) {
    return {sum + x.sum, max(pmax, sum + x.pmax), min(pmin, sum + x.pmin)};
  }
};

struct ST {
  const int N;
  vt<Node> st;
  ST(const int n) : N(n), st(n << 1) {} 
  void update(int i, const int v) {
    st[i += N] = {v, max(v, 0), min(v, 0)};
    while (i >>= 1)
      st[i] = st[i<<1] + st[i<<1|1];
  }
  Node query(int l, int r) {
    Node L = {0, 0, 0}, R = {0, 0, 0};
    for (l += N, r += N + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1)
        L = L + st[l++];
      if (r & 1)
        R = st[--r] + R;
    }
    return L + R;
  }
};

int sequence(int N, vt<int> A) {
  vt<vt<int>> inds(N, {0});
  FOR(i, 0, N-1)
    inds[--A[i]].push_back(i + 1);
  FOR(i, 0, N-1)
    inds[i].push_back(N + 1);
  ST st(N + 2);
  FOR(i, 1, N)
    st.update(i, 1);
  int ans = 1;
  FOR(x, 0, N-1) {
    for (const auto &i : inds[x])
      st.update(i, 0);
    if (x)
      for (const auto &i : inds[x-1])
        st.update(i, -1);
    vt<int> mx, mn;
    int tot = 0;
    FOR(i, 1, size(inds[x]) - 1) {
      const Node v = st.query(inds[x][i-1] + 1, inds[x][i] - 1);
      mx.push_back(tot + v.pmax);
      mn.push_back(tot + v.pmin);
      tot += v.sum;
    }
    FOR(i, 0, size(mx) - 1) {
      int lo = 0, hi = i - 1;
      while (lo < hi) {
        const int mid = lo + hi >> 1;
        if (mx[mid] + i >= mn[i] && i + mx[i] >= mn[mid])
          hi = mid;
        else
          lo = mid + 1;
      }
      ans = max(ans, i - lo);
      mx[i] -= i;
      mn[i] += i;
      if (i) {
        mx[i] = max(mx[i], mx[i-1]);
        mn[i] = min(mn[i], mn[i-1]);
      }
    }
  }
  return ans;
}

• 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