제출 #1111972

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1111972		abczz	서열 (APIO23_sequence)	C++17	100 / 100	1841 ms	81668 KiB

sequence

#include "sequence.h"
#include <iostream>
#include <vector>
#include <array>
#define ll int
using namespace std;

vector <ll> V[500000];

struct SegTree{
  ll st[4][2000000], lazy[4][2000000];
  void push(ll id) {
    for (int i=0; i<4; ++i) {
      if (!lazy[i][id]) continue;
      st[i][id*2] += lazy[i][id];
      st[i][id*2+1] += lazy[i][id];
      lazy[i][id*2] += lazy[i][id];
      lazy[i][id*2+1] += lazy[i][id];
      lazy[i][id] = 0;
    }
  }
  void build(ll id, ll l, ll r) {
    if (l == r) {
      st[0][id] = st[1][id] = st[2][id] = -l-1;
      st[3][id] = l+1;
      return;
    }
    ll mid = (l+r)/2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    st[0][id] = max(st[0][id*2], st[0][id*2+1]);
    st[1][id] = min(st[1][id*2], st[1][id*2+1]);
    st[2][id] = max(st[2][id*2], st[2][id*2+1]);
    st[3][id] = max(st[3][id*2], st[3][id*2+1]);
  }
  void update(ll id, ll l, ll r, ll ql, ll qr, ll z, ll w) {
    if (qr < l || r < ql) return;
    else if (ql <= l && r <= qr) {
      st[z][id] += w;
      lazy[z][id] += w;
      if (!z) st[1][id] += w, lazy[1][id] += w;
      return;
    }
    push(id);
    ll mid = (l+r)/2;
    update(id*2, l, mid, ql, qr, z, w);
    update(id*2+1, mid+1, r, ql, qr, z, w);
    st[z][id] = max(st[z][id*2], st[z][id*2+1]);
    st[1][id] = min(st[1][id*2], st[1][id*2+1]);
  }
  array<ll, 2> query(ll id, ll l, ll r, ll ql, ll qr, ll z) {
    if (qr < l || r < ql) {
      if (z != 0) return {-(ll)1e9, -(ll)1e9};
      else return {-(ll)1e9, (ll)1e9};
    }
    else if (ql <= l && r <= qr) return {st[z][id], st[z+1][id]};
    push(id);
    ll mid = (l+r)/2;
    auto a = query(id*2, l, mid, ql, qr, z);
    auto b = query(id*2+1, mid+1, r, ql, qr, z);
    if (!z) return {max(a[0], b[0]), min(a[1], b[1])};
    else return {max(a[0], b[0]), max(a[1], b[1])};
  }
  ll queryR(ll id, ll l, ll r, ll ql, ll qr, ll z, ll w) {
    if (qr < l || r < ql) return -1e9;
    else if (ql <= l && r <= qr) {
      ll mid = (l+r)/2;
      if (st[z][id] >= w) {
        if (l == r) return l;
        push(id);
        if (st[z][id*2+1] >= w) return queryR(id*2+1, mid+1, r, ql, qr, z, w);
        else return queryR(id*2, l, mid, ql, qr, z, w);
      }
      return -1e9;
    }
    push(id);
    ll mid = (l+r)/2, res = queryR(id*2+1, mid+1, r, ql, qr, z, w);
    if (res >= 0) return res;
    return queryR(id*2, l, mid, ql, qr, z, w);
  }
}ST;

ll a, b, c, d, s, f;
array<ll, 2> z;
int sequence(int N, std::vector<int> A) {
  f = 1;
  for (int i=0; i<N; ++i) {
    --A[i];
    V[A[i]].push_back(i);
  }
  ST.build(1, 0, N-1);
  for (int i=0; i<5e5; ++i) {
    for (auto u : V[i]) {
      ST.update(1, 0, N-1, u, N-1, 0, 1);
      ST.update(1, 0, N-1, u, N-1, 2, 2);
    }
    ll p = 0, k = 0, s;
    for (auto u : V[i]) {
      if (p < u) {
        auto tmp = ST.query(1, 0, N-1, u, u, 0);
        auto tmp2 = ST.query(1, 0, N-1, max(0, p-1), u, 0);
        a = tmp[0] - min((p == 0 ? 0 : (ll)1e9), tmp2[1]), b = -(tmp[0]-max((p == 0 ? 0 : -(ll)1e9), tmp2[0]));
      }
      else a = b = 0;
      a = max(0, a), b = max(0, b);
      if (u) z = ST.query(1, 0, N-1, u-1, u-1, 2);
      if (u) s = z[0];
      else s = 0;
      c = ST.queryR(1, 0, N-1, u, N-1, 2, -a+s);
      if (u) s = z[1];
      else s = 0;
      d = ST.queryR(1, 0, N-1, u, N-1, 3, -b+s);
      s = min(c, d);
      if (s != -1) {
        auto it = lower_bound(V[i].begin(), V[i].end(), s+1);
        it = prev(it);
        f = max(f, (ll)(it-V[i].begin())-k+1);
      }
      p = u+1, ++k;
    }
    for (auto u : V[i]) {
      ST.update(1, 0, N-1, u, N-1, 0, 1);
      ST.update(1, 0, N-1, u, N-1, 3, -2);
    }
  }
  return f;
}

• 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