Submission #1111954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111954		abczz	Sequence (APIO23_sequence)	C++17	50 / 100	1974 ms	183064 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 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]);
  }
  ll query(ll id, ll l, ll r, ll ql, ll qr, ll z) {
    if (qr < l || r < ql) return (z != 1 ? -1e9 : 1e9);
    else if (ql <= l && r <= qr) return st[z][id];
    push(id);
    ll mid = (l+r)/2;
    return (z != 1 ? max(query(id*2, l, mid, ql, qr, z), query(id*2+1, mid+1, r, ql, qr, z)) : min(query(id*2, l, mid, ql, qr, z), query(id*2+1, mid+1, r, ql, qr, z)));
  }
  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;
      push(id);
      if (st[z][id] >= w) {
        if (l == r) return l;
        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;
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.update(1, 0, N-1, i, N-1, 0, -1);
    ST.update(1, 0, N-1, i, N-1, 2, -1);
    ST.update(1, 0, N-1, i, N-1, 3, 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);
        a = tmp - min((p == 0 ? 0 : (ll)1e9), ST.query(1, 0, N-1, max(0, p-1), u, 1)), b = -(tmp-max((p == 0 ? 0 : -(ll)1e9), ST.query(1, 0, N-1, max(0, p-1), u, 0)));
      }
      else a = b = 0;
      a = max(0, a), b = max(0, b);
      if (u) s = ST.query(1, 0, N-1, u-1, u-1, 2);
      else s = 0;
      c = ST.queryR(1, 0, N-1, u, N-1, 2, -a+s);
      if (u) s = ST.query(1, 0, N-1, u-1, u-1, 3);
      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: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 22 / 22
• Subtask 7: 0 / 18