Submission #976332

#	Time	Username	Problem	Language	Result	Execution time	Memory
976332		MinaRagy06	Sequence (APIO23_sequence)	C++17	32 / 100	1022 ms	73608 KiB

sequence

#include <bits/stdc++.h>
#include "sequence.h"
#ifdef MINA
#include "grader.cpp"
#endif
using namespace std;
#define ll long long
#define SZ(x) (int) x.size()
#define md ((l + r) >> 1)

const int N = 500'005, inf = 1e9;

struct node {
	int mn, mx, lazy;
	node() {
		mn = inf;
		mx = -inf;
		lazy = 0;
	}
	friend node operator+(const node &l, const node &r) {
		node ret;
		ret.mn = min(l.mn, r.mn);
		ret.mx = max(l.mx, r.mx);
		return ret;
	}
};
struct segtree {
	node seg[1 << 20];
	void build(int i, int l, int r) {
		if (l == r) {
			seg[i].mn = seg[i].mx = 0;
			return;
		}
		build(i << 1, l, md);
		build(i << 1 | 1, md + 1, r);
		seg[i] = seg[i << 1] + seg[i << 1 | 1];
	}
	void process(int i, int l, int r) {
		if (l != r) {
			for (auto c : {i << 1, i << 1 | 1}) {
				seg[c].lazy += seg[i].lazy;
			}
		}
		seg[i].mn += seg[i].lazy;
		seg[i].mx += seg[i].lazy;
		seg[i].lazy = 0;
	}
	void add(int i, int l, int r, int s, int e, int v) {
		process(i, l, r);
		if (s <= l && r <= e) {
			seg[i].lazy += v;
			process(i, l, r);
			return;
		}
		if (r < s || e < l) {
			return;
		}
		add(i << 1, l, md, s, e, v);
		add(i << 1 | 1, md + 1, r, s, e, v);
		seg[i] = seg[i << 1] + seg[i << 1 | 1];
	}
	node get(int i, int l, int r, int s, int e) {
		process(i, l, r);
		if (s <= l && r <= e) {
			return seg[i];
		}
		if (r < s || e < l) {
			return node();
		}
		return get(i << 1, l, md, s, e) + get(i << 1 | 1, md + 1, r, s, e);
	}
} suf;
struct BIT {
	int n, bit[N];
	void init(int _n) {
		n = _n;
		for (int i = 0; i < n; i++) {
			bit[i] = inf;
		}
	}
	void upd(int x, int v) {
		for (int i = x; i < n; i |= i + 1) {
			bit[i] = min(bit[i], v);
		}
	}
	int get(int r) {
		if (r < 0) return inf;
		int mn = 1e9;
		for (int i = r; i >= 0; i = (i & (i + 1)) - 1) {
			mn = min(mn, bit[i]);
		}
		return mn;
	}
} bit;
int sequence(int n, vector<int> a) {
	vector<int> gud[n + 1];
	for (int i = 0; i <= n; i++) {
		gud[i].push_back(-1);
	}
	for (int i = 0; i < n; i++) {
		gud[a[i]].push_back(i);
	}
	for (int i = 0; i <= n; i++) {
		gud[i].push_back(n);
	}
	suf.build(1, 0, n);
	for (int i = 0; i < n; i++) {
		suf.add(1, 0, n, 0, i, 1);
	}
	int ans[n + 1];
	for (int i = 0; i < n; i++) {
		ans[i] = i;
	}
	for (int i = 0; i <= n; i++) {
		for (auto x : gud[i]) {
			suf.add(1, 0, n, 0, x, -1);
		}
		array<int, 2> vl[SZ(gud[i])], vr[SZ(gud[i])];
		for (int j = 1; j < SZ(gud[i]) - 1; j++) {
			vl[j] = {inf, -inf};
			node val = suf.get(1, 0, n, gud[i][j - 1] + 1, gud[i][j]);
			vl[j][0] = val.mn;
			vl[j][1] = val.mx;
		}
		for (int r = SZ(gud[i]) - 2; r >= 1; r--) {
			vr[r] = {inf, -inf};
			node val = suf.get(1, 0, n, gud[i][r] + 1, gud[i][r + 1]);
			vr[r][0] = val.mn;
			vr[r][1] = val.mx;
		}
		vector<array<int, 3>> v;
		for (int j = 1; j < SZ(gud[i]) - 1; j++) {
			v.push_back({vl[j][0], vl[j][1], j});
		}
		sort(v.begin(), v.end());
		vector<int> ask[SZ(v) + 1];
		for (int r = 1; r < SZ(gud[i]) - 1; r++) {
			int pos = lower_bound(v.begin(), v.end(), (array<int, 3>) {vr[r][0], 0, 0}) - v.begin();
			ask[pos].push_back(r);
		}
		vector<int> vals;
		for (int l = 1; l < SZ(gud[i]) - 1; l++) {
			vals.push_back(vl[l][0] + l);
		}
		sort(vals.begin(), vals.end());
		vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
		bit.init(SZ(vals) + 5);
		for (int i = SZ(v); i >= 0; i--) {
			if (i < SZ(v)) {
				int x = v[i][0] + v[i][2];
				int pos = lower_bound(vals.begin(), vals.end(), x) - vals.begin();
				bit.upd(pos, v[i][2]);
			}
			for (auto r : ask[i]) {
				int x = r + vr[r][1] + 1;
				int pos = lower_bound(vals.begin(), vals.end(), x + 1) - vals.begin() - 1;
				ans[r] = min(ans[r], bit.get(pos));
			}
		}
		vals.clear();
		for (int l = 1; l < SZ(gud[i]) - 1; l++) {
			vals.push_back(l - vl[l][1]);
		}
		sort(vals.begin(), vals.end());
		vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
		bit.init(SZ(vals) + 5);
		for (int i = 0; i <= SZ(v); i++) {
			for (auto r : ask[i]) {
				int x = r - vr[r][0] + 1;
				int pos = lower_bound(vals.begin(), vals.end(), x + 1) - vals.begin() - 1;
				ans[r] = min(ans[r], bit.get(pos));
			}
			if (i < SZ(v)) {
				int x = v[i][2] - v[i][1];
				int pos = lower_bound(vals.begin(), vals.end(), x) - vals.begin();
				bit.upd(pos, v[i][2]);
			}
		}
// 		for (int l = 1; l <= r; l++) {
// 			if (vr[0] <= vl[l][0]) {
// 				if (vl[l][0] + l <= r + vr[1] + 1) {
// 					ans = max(ans, r - l + 1);
// 					break;
// 				}
// 			} else {
//				//vr[0] >= vl[l][0]
// 				if (l - vl[l][1] <= r - vr[0] + 1) {
// 					ans = max(ans, r - l + 1);
// 				}
// 			}
// 		}
		for (auto x : gud[i]) {
			suf.add(1, 0, n, 0, x, -1);
		}
	}
	int mx = 0;
	for (int i = 0; i < n; i++) {
		mx = max(mx, i - ans[i] + 1);
	}
	return mx;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 17
• Subtask 3: 7 / 7
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18