Submission #751051

#	Time	Username	Problem	Language	Result	Execution time	Memory
751051		maeola	Sequence (APIO23_sequence)	C++17	100 / 100	1607 ms	87988 KiB

sequence

#include "sequence.h"

#include <algorithm>
#include <vector>
using namespace std;

struct Node
{
	int sum, neg, pos;
};

Node nodes[2000005];

struct Sus
{
	int mn;
	bool r;
};

Sus sussy[13000005];

void wind() { sussy[1].r = true; }

void clean(int i)
{
	auto &node = sussy[i];
	if (node.r)
	{
		node.mn = 1e9;
		sussy[2 * i].r = true;
		sussy[2 * i + 1].r = true;
		node.r = false;
	}
}

void simple_upd(int i, int l, int r, int p, int x)
{
	clean(i);
	auto &node = sussy[i];
	if (p < l or p > r)
		return;
	if (l == r)
	{
		node.mn = min(node.mn, x);
		return;
	}
	int m = l + (r - l) / 2;
	simple_upd(2 * i, l, m, p, x);
	simple_upd(2 * i + 1, m + 1, r, p, x);
	node.mn = min(sussy[2 * i].mn, sussy[2 * i + 1].mn);
}

int simple_query(int i, int l, int r, int ql, int qr)
{
	clean(i);
	if (qr < l or ql > r)
		return 1e9;
	if (ql <= l and qr >= r)
		return sussy[i].mn;
	// int m = (l + r) / 2;
	int m = l + (r - l) / 2;
	return min(simple_query(2 * i, l, m, ql, qr),
		   simple_query(2 * i + 1, m + 1, r, ql, qr));
}

// struct Sus
// {
// 	int mn, lazy;
// 	bool r;
// };
//
// Sus sussy[8000005];
//
// void wind() {
// 	sussy[1].r = true;
// }
//
// void clean(int i) {
// 	auto &node = sussy[i];
// 	if (node.r)
// 	{
// 		node.mn = 1e9;
// 		node.lazy = 1e9;
// 		sussy[2 * i].r = true;
// 		sussy[2 * i + 1].r = true;
// 		node.r = false;
// 	}
// 	node.mn = min(node.mn, node.lazy);
// 	sussy[2 * i].lazy = min(sussy[2 * i].lazy, node.lazy);
// 	sussy[2 * i + 1].lazy = min(sussy[2 * i + 1].lazy, node.lazy);
// }
//
// int set_query(int i, int l, int r, int ql, int qr, int v) {
// 	clean(i);
// 	auto &node = sussy[i];
// 	if (qr < l or ql > r)
// 		return 1e9;
// 	if (ql <= l and qr >= r)
// 	{
// 		node.lazy = min(node.lazy, v);
// 		clean(i);
// 		return node.mn;
// 	}
// 	// int m = (l + r) / 2;
// 	int m = l + (r - l) / 2;
// 	auto a = set_query(2 * i, l, m, ql, qr, v);
// 	auto b = set_query(2 * i + 1, m + 1, r, ql, qr, v);
// 	node.mn = min(sussy[2 * i].mn, sussy[2 * i + 1].mn);
// 	return min(a, b);
// }

void reset()
{
	for (auto &x : nodes)
		x.sum = x.neg = x.pos = 0;
}

Node comb(const Node &a, const Node &b)
{
	return {a.sum + b.sum, min(a.neg, a.sum + b.neg),
		max(a.pos, a.sum + b.pos)};
}

void upd(int i, int l, int r, int p, int x)
{
	if (p < l or p > r)
		return;
	auto &node = nodes[i];
	if (l == r)
	{
		node.sum = x;
		node.neg = min(x, 0);
		node.pos = max(x, 0);
		return;
	}
	int m = (l + r) / 2;
	upd(2 * i, l, m, p, x);
	upd(2 * i + 1, m + 1, r, p, x);
	node = comb(nodes[2 * i], nodes[2 * i + 1]);
}

Node query(int i, int l, int r, int ql, int qr)
{
	if (qr < l or ql > r)
		return {0, 0, 0};
	if (ql <= l and qr >= r)
		return nodes[i];
	int m = (l + r) / 2;
	return comb(query(2 * i, l, m, ql, qr),
		    query(2 * i + 1, m + 1, r, ql, qr));
}

vector<int> possy[500005];

constexpr int L = -1e6 - 5;
constexpr int R = -L;

int sequence(int N, vector<int> A)
{
	reset();
	for (auto &a : possy)
		a.clear();
	for (int i = 0; i < N; i++)
	{
		possy[A[i]].push_back(i);
		upd(1, 0, N - 1, i, 1);
	}
	int ans = 1;
	// for (int i = L; i <= R; i++)
	// 	simple_upd(1, L, R, i, 1e9, true);
	for (int q = 1; q <= N; q++)
	{
		auto &b = possy[q];
		if (b.empty())
			continue;
		b.push_back(N);
		vector<pair<int, int>> segs;
		int bg = 0;
		int ptr = 0;
		for (int p : b)
		{
			auto h = query(1, 0, N - 1, bg, p - 1);
			segs.push_back({ptr + h.neg, ptr + h.pos});
			ptr += h.sum;
			bg = p + 1;
		}
		int m = (int)segs.size();
		wind();
		vector<tuple<int, int, int>> from, to;
		for (int i = 0; i < m; i++)
		{
			auto [a, b] = segs[i];
			from.push_back({a + i, b - i, i});
			to.push_back({b + i, a - i, i});
		}
		sort(from.begin(), from.end());
		sort(to.begin(), to.end());
		ptr = 0;
		for (auto [b, a, i] : to)
		{
			while (ptr < (int)from.size() and
			       get<0>(from[ptr]) <= b)
			{
				auto [p, q, j] = from[ptr];
				simple_upd(1, L, R, q, j);
				ptr++;
			}
			int g = simple_query(1, L, R, a, R);
			ans = max(ans, i - g);
		}
		// for (auto [p, q, j] : from)
		// {
		// 	simple_upd(1, L, R, q, 1e9, true);
		// }
		// for (int i = 0; i < m; i++)
		// {
		// 	auto [a, b] = segs[i];
		// 	int f = set_query(1, -1e6 - 5, 1e6 + 5, a - i, b + i,
		// i); 	ans = max(ans, i - f);
		// }
		// for (int i = 0; i < m; i++)
		// {
		// 	for (int j = i + 1; j < m; j++)
		// 	{
		// 		int d = j - i;
		// 		auto [a, b] = segs[i];
		// 		auto [x, y] = segs[j];
		// 		if (not (a > y + d or b < x - d))
		// 		{
		// 			ans = max(ans, d);
		// 		}
		// 	}
		// }
		for (int p : b)
			upd(1, 0, N - 1, p, -1);
	}
	return ans;
}

• 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