Submission #1211393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211393		k1r1t0	Sequence (APIO23_sequence)	C++20	100 / 100	825 ms	69836 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

const int N = 510000;
const int INF = (int)(2e9);

struct segtree {
	vector<int> mn, mx, cc;
	segtree(int n) {
		mn = mx = cc = vector<int>(4 * n + 1, 0);
	}
	void merge(int v) {
		mn[v] = min(mn[v * 2 + 0], mn[v * 2 + 1]) + cc[v];
		mx[v] = max(mx[v * 2 + 0], mx[v * 2 + 1]) + cc[v];
	}
	void upd(int v, int l, int r, int ql, int qr, int x) {
		if (qr < l || r < ql) return;
		if (ql <= l && r <= qr) {
			cc[v] += x;
			mn[v] += x;
			mx[v] += x;
			return;
		}
		int mid = (l + r) / 2;
		upd(v * 2 + 0, l, mid, ql, qr, x);
		upd(v * 2 + 1, mid + 1, r, ql, qr, x);
		merge(v);
	}
	int get_min(int v, int l, int r, int ql, int qr) {
		if (qr < l || r < ql) return INF;
		if (ql <= l && r <= qr) return mn[v];
		int mid = (l + r) / 2;
		return min(get_min(v * 2 + 0, l, mid, ql, qr), get_min(v * 2 + 1, mid + 1, r, ql, qr)) + cc[v];
	}
	int get_max(int v, int l, int r, int ql, int qr) {
		if (qr < l || r < ql) return -INF;
		if (ql <= l && r <= qr) return mx[v];
		int mid = (l + r) / 2;
		return max(get_max(v * 2 + 0, l, mid, ql, qr), get_max(v * 2 + 1, mid + 1, r, ql, qr)) + cc[v];
	}
};

vector<int> pos[N];

int sequence(int N, vector<int> A) {
	int ans = 0;
	reverse(begin(A), end(A));
	A.push_back(0);
	reverse(begin(A), end(A));
	for (int i = 1; i <= N; i++)
		pos[A[i]].push_back(i);
	segtree cur(N + 1);
	for (int i = 1; i <= N; i++)
		cur.upd(1, 0, N, i, N, 1);
	for (int i = 1; i <= N; i++) {
		for (int k : pos[i - 0]) cur.upd(1, 0, N, k, N, -1);
		for (int k : pos[i - 1]) cur.upd(1, 0, N, k, N, -1);
		vector<array<int, 2>> base;
		pos[i].push_back(N + 1);
		int ptr = 0;
		for (int k : pos[i]) {
			base.push_back({cur.get_min(1, 0, N, ptr, k - 1), cur.get_max(1, 0, N, ptr, k - 1)});
			ptr = k;
		}
		pos[i].pop_back();
		int m = base.size();
		vector<array<int, 2>> pref = base, suff = base;
		for (int i = 1; i < m; i++) {
			pref[i][0] = min(pref[i][0], pref[i - 1][0] - 1);
			pref[i][1] = max(pref[i][1], pref[i - 1][1] + 1);
		}
		for (int i = m - 2; i >= 0; i--) {
			suff[i][0] = min(suff[i][0], suff[i + 1][0] - 1);
			suff[i][1] = max(suff[i][1], suff[i + 1][1] + 1);
		}
		ptr = 0;
		for (int l = 0; l < m; l++) {
			while (ptr + 1 < m) {
				int len = ptr + 1 - l;
				int lp = max(pref[l][0], suff[ptr + 1][0] - len);
				int rp = min(pref[l][1], suff[ptr + 1][1] + len);
				if (lp > rp) break;
				ptr++;
			}
			ans = max(ans, ptr - l);
		}
	}
	return ans;
}

/*

#include <cassert>
#include <cstdio>

#include <vector>

int32_t main() {
  int N;
  assert(1 == scanf("%d", &N));

  std::vector<int> A(N);
  for (int i = 0; i < N; ++i) {
    assert(1 == scanf("%d", &A[i]));
  }

  int result = sequence(N, A);
  printf("%d\n", result);
  return 0;
}

//*/

• 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