Submission #749215

#	Time	Username	Problem	Language	Result	Execution time	Memory
749215		SanguineChameleon	Sequence (APIO23_sequence)	C++17	100 / 100	1039 ms	166776 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;

struct node {
	int mi, mx, lazy;

	node(): mi(0), mx(0), lazy(0) {};

	node(int _mi, int _mx): mi(_mi), mx(_mx), lazy(0) {};
};

const int maxn = 5e5 + 20;
int a[maxn];
vector<int> pos[maxn];
vector<int> pref[maxn][2];
vector<int> suf[maxn][2];
node tree[maxn * 4];
int n;

node merge(node L, node R) {
	return node(min(L.mi, R.mi), max(L.mx, R.mx));
}

void build(int id, int lt, int rt) {
	if (lt == rt) {
		tree[id] = node(lt, lt);
		return;
	}
	int mt = (lt + rt) / 2;
	build(id * 2, lt, mt);
	build(id * 2 + 1, mt + 1, rt);
	tree[id] = merge(tree[id * 2], tree[id * 2 + 1]);
}

void push(int id) {
	tree[id * 2].lazy += tree[id].lazy;
	tree[id * 2].mi += tree[id].lazy;
	tree[id * 2].mx += tree[id].lazy;
	tree[id * 2 + 1].lazy += tree[id].lazy;
	tree[id * 2 + 1].mi += tree[id].lazy;
	tree[id * 2 + 1].mx += tree[id].lazy;
	tree[id].lazy = 0;
}


void update(int id, int lt, int rt, int ql, int qr) {
	if (lt == ql && rt == qr) {
		tree[id].lazy -= 2;
		tree[id].mi -= 2;
		tree[id].mx -= 2;
		return;
	}
	push(id);
	int mt = (lt + rt) / 2;
	if (qr <= mt) {
		update(id * 2, lt, mt, ql, qr);
	}
	else if (ql >= mt + 1) {
		update(id * 2 + 1, mt + 1, rt, ql, qr);
	}
	else {
		update(id * 2, lt, mt, ql, mt);
		update(id * 2 + 1, mt + 1, rt, mt + 1, qr);
	}
	tree[id] = merge(tree[id * 2], tree[id * 2 + 1]);
}

node get(int id, int lt, int rt, int ql, int qr) {
	if (lt == ql && rt == qr) {
		return tree[id];
	}
	push(id);
	int mt = (lt + rt) / 2;
	if (qr <= mt) {
		return get(id * 2, lt, mt, ql, qr);
	}
	else if (ql >= mt + 1) {
		return get(id * 2 + 1, mt + 1, rt, ql, qr);
	}
	else {
		return merge(get(id * 2, lt, mt, ql, mt), get(id * 2 + 1, mt + 1, rt, mt + 1, qr));
	}
}

bool check(int k) {
	for (int i = 1; i <= n; i++) {
		for (int j = k - 1; j < (int)pos[i].size(); j++) {
			if (suf[i][0][j] >= pref[i][0][j - (k - 1)] && suf[i][1][j] <= pref[i][1][j - (k - 1)]) {
				return true;
			}
		}
	}
	return false;
}

int sequence(int _N, vector<int> _A) {
	n = _N;
	for (int i = 1; i <= n; i++) {
		a[i] = _A[i - 1];
	}
	for (int i = 1; i <= n; i++) {
		pos[a[i]].push_back(i);
	}
	build(1, 0, n);
	for (int i = 1; i <= n; i++) {
		for (auto p: pos[i]) {
			pref[i][0].push_back(get(1, 0, n, 0, p - 1).mi);
			suf[i][0].push_back(get(1, 0, n, p, n).mx);
		}
		for (auto p: pos[i]) {
			update(1, 0, n, p, n);
		}
		for (auto p: pos[i]) {
			pref[i][1].push_back(get(1, 0, n, 0, p - 1).mx);
			suf[i][1].push_back(get(1, 0, n, p, n).mi);
		}
	}
	int res = 1;
	int lt = 1;
	int rt = n;
	while (lt <= rt) {
		int mt = (lt + rt) / 2;
		if (check(mt)) {
			res = mt;
			lt = mt + 1;
		}
		else {
			rt = mt - 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