Submission #1201186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201186		aykhn	Sequence (APIO23_sequence)	C++20	100 / 100	1856 ms	448516 KiB

sequence

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

using namespace std;

#define inf 0x3F3F3F3F

struct DATA
{
  int s1 = 0, s2 = 0, mxp1 = 0, mxp2 = 0, mxs1 = 0, mxs2 = 0, mnp1 = 0, mnp2 = 0, mns1 = 0, mns2 = 0;
};

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

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

DATA combine(DATA x, DATA y)
{
  return {
    x.s1 + y.s1, 
    x.s2 + y.s2, 
    max(x.mxp1, x.s1 + y.mxp1), 
    max(x.mxp2, x.s2 + y.mxp2), 
    max(y.mxs1, y.s1 + x.mxs1), 
    max(y.mxs2, y.s2 + x.mxs2), 
    min(x.mnp1, x.s1 + y.mnp1), 
    min(x.mnp2, x.s2 + y.mnp2), 
    min(y.mns1, y.s1 + x.mns1),
    min(y.mns2, y.s2 + x.mns2),
  };
}
void upd(int l, int r, int x, int ind, int val)
{
  if (l == r)
  {
    if (val != 0) st[x] = {val, val, max(0, val), max(0, val), max(0, val), max(0, val), min(0, val), min(0, val), min(0, val), min(0, val)};
    else st[x] = {1, -1, 1, 0, 1, 0, 0, -1, 0, -1};
    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, 0, 0, 0, 0};
  }
  if (l > rx || r < lx) return {0, 0, 0, 0, 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));
}

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);
    for (int r = 0, l = 0; r < v.size(); r++)
    {
      while (l <= 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.s1 - A;
        DATA L = get(0, N - 1, 1, 0, v[l] - 1);
        DATA R = get(0, N - 1, 1, v[r] + 1, N - 1);
        int mn = B + L.mns2 + R.mnp2, mx = B + L.mxs1 + R.mxp1;
        if ((mn <= 0 && 0 <= mx) || min(abs(mn), abs(mx)) <= A) 
        {
          res = max(res, A);
          break;
        }
        l++;
      }
    }
    for (int &i : v) upd(0, N - 1, 1, i, -1);
  }
  return res;
}

• 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