oj.uz

Submission #751051

# Submission time Handle Problem Language Result Execution time Memory
751051 2023-05-31T01:03:14 Z maeola Sequence (APIO23_sequence) C++17
100 / 100
 1607 ms 87988 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35540 KB Output is correct
2 Correct 19 ms 35540 KB Output is correct
3 Correct 23 ms 35500 KB Output is correct
4 Correct 18 ms 35512 KB Output is correct
5 Correct 18 ms 35500 KB Output is correct
6 Correct 20 ms 35552 KB Output is correct
7 Correct 18 ms 35540 KB Output is correct
8 Correct 20 ms 35564 KB Output is correct
9 Correct 19 ms 35540 KB Output is correct
10 Correct 19 ms 35540 KB Output is correct
11 Correct 19 ms 35588 KB Output is correct
12 Correct 18 ms 35540 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35540 KB Output is correct
2 Correct 19 ms 35540 KB Output is correct
3 Correct 23 ms 35500 KB Output is correct
4 Correct 18 ms 35512 KB Output is correct
5 Correct 18 ms 35500 KB Output is correct
6 Correct 20 ms 35552 KB Output is correct
7 Correct 18 ms 35540 KB Output is correct
8 Correct 20 ms 35564 KB Output is correct
9 Correct 19 ms 35540 KB Output is correct
10 Correct 19 ms 35540 KB Output is correct
11 Correct 19 ms 35588 KB Output is correct
12 Correct 18 ms 35540 KB Output is correct
13 Correct 22 ms 35704 KB Output is correct
14 Correct 22 ms 35772 KB Output is correct
15 Correct 23 ms 35740 KB Output is correct
16 Correct 20 ms 35668 KB Output is correct
17 Correct 20 ms 35680 KB Output is correct
18 Correct 24 ms 35724 KB Output is correct
19 Correct 23 ms 35764 KB Output is correct
20 Correct 23 ms 35724 KB Output is correct
21 Correct 23 ms 35720 KB Output is correct
22 Correct 21 ms 35736 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35540 KB Output is correct
2 Correct 1071 ms 82548 KB Output is correct
3 Correct 1062 ms 82616 KB Output is correct
4 Correct 656 ms 62060 KB Output is correct
5 Correct 997 ms 81860 KB Output is correct
6 Correct 1101 ms 81912 KB Output is correct
7 Correct 663 ms 59556 KB Output is correct
8 Correct 700 ms 58536 KB Output is correct
9 Correct 659 ms 59664 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35540 KB Output is correct
2 Correct 696 ms 66172 KB Output is correct
3 Correct 695 ms 73024 KB Output is correct
4 Correct 686 ms 73008 KB Output is correct
5 Correct 702 ms 79768 KB Output is correct
6 Correct 666 ms 70100 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1607 ms 87976 KB Output is correct
2 Correct 1420 ms 87976 KB Output is correct
3 Correct 1428 ms 87396 KB Output is correct
4 Correct 1469 ms 87336 KB Output is correct
5 Correct 1257 ms 83972 KB Output is correct
6 Correct 1223 ms 84008 KB Output is correct
7 Correct 1085 ms 82912 KB Output is correct
8 Correct 1079 ms 82528 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35540 KB Output is correct
2 Correct 19 ms 35540 KB Output is correct
3 Correct 23 ms 35500 KB Output is correct
4 Correct 18 ms 35512 KB Output is correct
5 Correct 18 ms 35500 KB Output is correct
6 Correct 20 ms 35552 KB Output is correct
7 Correct 18 ms 35540 KB Output is correct
8 Correct 20 ms 35564 KB Output is correct
9 Correct 19 ms 35540 KB Output is correct
10 Correct 19 ms 35540 KB Output is correct
11 Correct 19 ms 35588 KB Output is correct
12 Correct 18 ms 35540 KB Output is correct
13 Correct 22 ms 35704 KB Output is correct
14 Correct 22 ms 35772 KB Output is correct
15 Correct 23 ms 35740 KB Output is correct
16 Correct 20 ms 35668 KB Output is correct
17 Correct 20 ms 35680 KB Output is correct
18 Correct 24 ms 35724 KB Output is correct
19 Correct 23 ms 35764 KB Output is correct
20 Correct 23 ms 35724 KB Output is correct
21 Correct 23 ms 35720 KB Output is correct
22 Correct 21 ms 35736 KB Output is correct
23 Correct 205 ms 43020 KB Output is correct
24 Correct 230 ms 43076 KB Output is correct
25 Correct 216 ms 43032 KB Output is correct
26 Correct 136 ms 42080 KB Output is correct
27 Correct 147 ms 42060 KB Output is correct
28 Correct 161 ms 42116 KB Output is correct
29 Correct 124 ms 41648 KB Output is correct
30 Correct 134 ms 41576 KB Output is correct
31 Correct 110 ms 42812 KB Output is correct
32 Correct 196 ms 43884 KB Output is correct
33 Correct 220 ms 43196 KB Output is correct
34 Correct 208 ms 43260 KB Output is correct
35 Correct 228 ms 43016 KB Output is correct
36 Correct 207 ms 42956 KB Output is correct
37 Correct 192 ms 42936 KB Output is correct
38 Correct 228 ms 43136 KB Output is correct

Subtask #7
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35540 KB Output is correct
2 Correct 19 ms 35540 KB Output is correct
3 Correct 23 ms 35500 KB Output is correct
4 Correct 18 ms 35512 KB Output is correct
5 Correct 18 ms 35500 KB Output is correct
6 Correct 20 ms 35552 KB Output is correct
7 Correct 18 ms 35540 KB Output is correct
8 Correct 20 ms 35564 KB Output is correct
9 Correct 19 ms 35540 KB Output is correct
10 Correct 19 ms 35540 KB Output is correct
11 Correct 19 ms 35588 KB Output is correct
12 Correct 18 ms 35540 KB Output is correct
13 Correct 22 ms 35704 KB Output is correct
14 Correct 22 ms 35772 KB Output is correct
15 Correct 23 ms 35740 KB Output is correct
16 Correct 20 ms 35668 KB Output is correct
17 Correct 20 ms 35680 KB Output is correct
18 Correct 24 ms 35724 KB Output is correct
19 Correct 23 ms 35764 KB Output is correct
20 Correct 23 ms 35724 KB Output is correct
21 Correct 23 ms 35720 KB Output is correct
22 Correct 21 ms 35736 KB Output is correct
23 Correct 1071 ms 82548 KB Output is correct
24 Correct 1062 ms 82616 KB Output is correct
25 Correct 656 ms 62060 KB Output is correct
26 Correct 997 ms 81860 KB Output is correct
27 Correct 1101 ms 81912 KB Output is correct
28 Correct 663 ms 59556 KB Output is correct
29 Correct 700 ms 58536 KB Output is correct
30 Correct 659 ms 59664 KB Output is correct
31 Correct 696 ms 66172 KB Output is correct
32 Correct 695 ms 73024 KB Output is correct
33 Correct 686 ms 73008 KB Output is correct
34 Correct 702 ms 79768 KB Output is correct
35 Correct 666 ms 70100 KB Output is correct
36 Correct 1607 ms 87976 KB Output is correct
37 Correct 1420 ms 87976 KB Output is correct
38 Correct 1428 ms 87396 KB Output is correct
39 Correct 1469 ms 87336 KB Output is correct
40 Correct 1257 ms 83972 KB Output is correct
41 Correct 1223 ms 84008 KB Output is correct
42 Correct 1085 ms 82912 KB Output is correct
43 Correct 1079 ms 82528 KB Output is correct
44 Correct 205 ms 43020 KB Output is correct
45 Correct 230 ms 43076 KB Output is correct
46 Correct 216 ms 43032 KB Output is correct
47 Correct 136 ms 42080 KB Output is correct
48 Correct 147 ms 42060 KB Output is correct
49 Correct 161 ms 42116 KB Output is correct
50 Correct 124 ms 41648 KB Output is correct
51 Correct 134 ms 41576 KB Output is correct
52 Correct 110 ms 42812 KB Output is correct
53 Correct 196 ms 43884 KB Output is correct
54 Correct 220 ms 43196 KB Output is correct
55 Correct 208 ms 43260 KB Output is correct
56 Correct 228 ms 43016 KB Output is correct
57 Correct 207 ms 42956 KB Output is correct
58 Correct 192 ms 42936 KB Output is correct
59 Correct 228 ms 43136 KB Output is correct
60 Correct 1553 ms 82648 KB Output is correct
61 Correct 1552 ms 82824 KB Output is correct
62 Correct 1521 ms 82772 KB Output is correct
63 Correct 983 ms 75528 KB Output is correct
64 Correct 989 ms 75532 KB Output is correct
65 Correct 1043 ms 75368 KB Output is correct
66 Correct 693 ms 73888 KB Output is correct
67 Correct 719 ms 73764 KB Output is correct
68 Correct 660 ms 73688 KB Output is correct
69 Correct 1134 ms 87988 KB Output is correct
70 Correct 1538 ms 82096 KB Output is correct
71 Correct 1426 ms 82476 KB Output is correct
72 Correct 1402 ms 82180 KB Output is correct
73 Correct 1442 ms 82304 KB Output is correct
74 Correct 1377 ms 80976 KB Output is correct
75 Correct 1508 ms 82432 KB Output is correct