Submission #1201164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201164		aykhn	Sequence (APIO23_sequence)	C++20	41 / 100	2108 ms	585188 KiB

sequence

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

using namespace std;

#define inf 0x3F3F3F3F

struct DATA
{
  int s = 0, mxp = 0, mxs = 0, mnp = 0, mns = 0;
};

const int MXN = 5e5 + 5;
const int B = 300;

DATA st[MXN << 2];
set<array<int, 2>> stmx[MXN << 4];

DATA combine(DATA x, DATA y)
{
  return {x.s + y.s, max(x.mxp, x.s + y.mxp), max(y.mxs, y.s + x.mxs), min(x.mnp, x.s + y.mnp), min(y.mns, y.s + x.mns)};
}
void upd(int l, int r, int x, int ind, int val)
{
  if (l == r)
  {
    st[x] = {val, max(0, val), max(0, val), min(0, val), min(0, val)};
    return;
  }
  int mid = (l + r) >> 1;
  if (ind <= mid) upd(l, mid, 2*x, ind, val);
  else upd(mid + 1, r, 2*x + 1, ind, val);
  st[x] = combine(st[2*x], st[2*x + 1]);
}
DATA get(int l, int r, int x, int lx, int rx)
{
  if (lx > rx) return {0, 0, 0, 0, 0};
  if (l > rx || r < lx) return {0, 0, 0, 0, 0};
  if (l >= lx && r <= rx) return st[x];
  int mid = (l + r) >> 1;
  return combine(get(l, mid, 2*x, lx, rx), get(mid + 1, r, 2*x + 1, lx, rx));
}
void build(int l, int r, int x)
{
  stmx[x] = {{-inf, inf}};
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(l, mid, 2*x);
  build(mid + 1, r, 2*x + 1);
}
void add(set<array<int, 2>> &st, int pos, int val)
{
  auto it = prev(st.upper_bound({pos, inf}));
  if (val >= (*it)[1]) return;
  while (1)
  {
    auto it = st.lower_bound({pos, -inf});
    if (it != st.end() && (*it)[1] >= val) st.erase(it);
    else break;
  }
  st.insert({pos, val});
}
int query(set<array<int, 2>> &st, int pos)
{
  return (*prev(st.upper_bound({pos, inf})))[1];
}
void updmn(int l, int r, int x, int ind, int pos, int val)
{
  add(stmx[x], pos, val);
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (ind <= mid) updmn(l, mid, 2*x, ind, pos, val);
  else updmn(mid + 1, r, 2*x + 1, ind, pos, val);
}
int getmn(int l, int r, int x, int lx, int rx, int val)
{
  if (l > rx || r < lx) return inf;
  if (l >= lx && r <= rx) return query(stmx[x], val);
  int mid = (l + r) >> 1;
  return min(getmn(l, mid, 2*x, lx, rx, val), getmn(mid + 1, r, 2*x + 1, lx, rx, val));
}

int sequence(int N, vector<int> A)
{
  vector<int> idx[N + 1];
  for (int i = 0; i < N; i++) idx[A[i]].push_back(i);
  for (int i = 0; i < N; i++) upd(0, N - 1, 1, i, 1);
  int res = 1;
  for (int val = 1; val <= N; val++)
  {
    vector<int> &v = idx[val];
    for (int &i : v) upd(0, N - 1, 1, i, 0);
    if (idx[val].size() <= B)
    {
      for (int l = 0; l < v.size(); l++)
      {
        for (int r = l; r < v.size(); r++)
        {
          DATA x = get(0, N - 1, 1, v[l], v[r]);
          // A = a, B = x - y
          int A = r - l + 1;
          int B = x.s;
          DATA L = get(0, N - 1, 1, 0, v[l] - 1);
          DATA R = get(0, N - 1, 1, v[r], N - 1);
          int mn = B + L.mns + R.mnp, mx = B + L.mxs + R.mxp;
          if (mn <= 0 && 0 <= mx) res = max(res, A);
          else if (min(abs(mn), abs(mx)) <= A) res = max(res, A);
        }
      }
    }
    for (int &i : v) upd(0, N - 1, 1, i, -1);
  }
  for (int val = 1; val <= N; val++)
  {
    vector<int> &v = idx[val];
    if (v.size() <= B) continue;
    build(-N, N, 1);
    updmn(-N, N, 1, 0, 0, 0);
    int x = 0, y = 0, a = 0;
    for (int i = 0; i < N; i++)
    {
      if (A[i] == val) x++, y++, a++;
      else if (A[i] < val) x++, y--;
      else x--, y++;
      res = max(res, a - getmn(-N, N, 1, -N, x, y));
      updmn(-N, N, 1, x, y, a);
    }
  }
  return res;
}

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