Submission #985223

#	Time	Username	Problem	Language	Result	Execution time	Memory
985223		CrazyBotBoy	Sequence (APIO23_sequence)	C++17	100 / 100	515 ms	51012 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<int, 2>;
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
const int MAXT = 1050000;

struct node {
	int sum, pmin, pmax;
	node() { sum = pmin = pmax = 0; }
	node(int x) {
		sum = x;
		pmin = min(x, 0);
		pmax = max(x, 0);
	}
	node operator+(const node &nd) {
		node ret;
		ret.sum = sum + nd.sum;
		ret.pmin = min(pmin, sum + nd.pmin);
		ret.pmax = max(pmax, sum + nd.pmax);
		return ret;
	}
};

struct bit {
	int tree[MAXT];
	void init() { memset(tree, 0x3f, sizeof(tree)); }
	void add(int x, int v) {
		for (int i = x + 2; i < MAXT; i += i & -i)
			tree[i] = min(tree[i], v);
	}
	int query(int x) {
		int ret = 1e9;
		for (int i = x + 2; i; i -= i & -i)
			ret = min(ret, tree[i]);
		return ret;
	}
	void flush(int x) {
		for (int i = x + 2; i < MAXT; i += i & -i)
			tree[i] = 1e9;
	}
} bit;
struct seg {
	node tree[MAXT];
	int lim;
	void init(int n, int v) {
		for (lim = 1; lim <= n; lim <<= 1)
			;
		for (int i = 0; i < n; i++)
			tree[i + lim] = node(v);
		for (int i = lim - 1; i; i--)
			tree[i] = tree[2 * i] + tree[2 * i + 1];
	}
	void upd(int x, int v) {
		x += lim;
		tree[x] = node(v);
		while (x > 1) {
			x >>= 1;
			tree[x] = tree[2 * x] + tree[2 * x + 1];
		}
	}
	node query(int l, int r) {
		if (l > r)
			return node();
		l += lim;
		r += lim;
		node L, R;
		while (l < r) {
			if (l % 2 == 1)
				L = L + tree[l++];
			if (r % 2 == 0)
				R = tree[r--] + R;
			l >>= 1;
			r >>= 1;
		}
		if (l == r)
			L = L + tree[l];
		return L + R;
	}
} seg;

int sequence(int n, std::vector<int> a) {
	bit.init();
	vector<vector<int>> indices(n);
	for (int i = 0; i < n; i++) {
		a[i]--;
		indices[a[i]].push_back(i);
	}
	seg.init(n, 1);
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (sz(indices[i]) == 0)
			continue;
		vector<array<int, 3>> PL(sz(indices[i]) + 1), PR(sz(indices[i]) + 1);
		vector<int> vect;
		for (int j = 0; j <= sz(indices[i]); j++) {
			int l = (j ? (indices[i][j - 1]) : -1);
			int r = (j < sz(indices[i]) ? indices[i][j] : n);
			auto lsum = seg.query(0, l).sum;
			auto msum = seg.query(l + 1, r - 1);
			int sx = lsum + msum.pmin;
			int ex = lsum + msum.pmax;
			int sy = 2 * j - ex;
			int ey = 2 * j - sx;
			PL[j] = {sx, sy, j};
			PR[j] = {ex, ey, j};
			vect.push_back(sy);
			vect.push_back(ey);
		}

		sort(all(vect));
		for (auto &[_, y, __] : PL) {
			y = lower_bound(all(vect), y) - vect.begin();
		}
		for (auto &[_, y, __] : PR) {
			y = lower_bound(all(vect), y) - vect.begin();
		}
		sort(all(PL));
		sort(all(PR));
		int j = 0;
		for (int i = 0; i < sz(PR); i++) {
			while (j < sz(PL) && PL[j] <= PR[i]) {
				bit.add(PL[j][1], PL[j][2]);
				j++;
			}
			ans = max(ans, PR[i][2] - bit.query(PR[i][1]));
		}
		for (int k = 0; k < j; k++)
			bit.flush(PL[k][1]);
		for (auto &q : indices[i]) {
			seg.upd(q, -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