Submission #1190172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190172		kirito	Sequence (APIO23_sequence)	C++20	100 / 100	767 ms	80804 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

const int N = 510000;

struct segtree {
	vector<int> vmn, vmx, lz;
	segtree() {}
	segtree(int n) {
		vmn = vmx = lz = vector<int>(4 * n + 1, 0);
	}
	void push(int v, int l, int r) {
		if (lz[v] == 0) return;
		vmn[v] += lz[v];
		vmx[v] += lz[v];
		if (l != r) {
			lz[v * 2 + 0] += lz[v];
			lz[v * 2 + 1] += lz[v];
		}
		lz[v] = 0;
	}
	void upd(int v, int l, int r, int ql, int qr, int x) {
		push(v, l, r);
		if (qr < l || r < ql) return;
		if (ql <= l && r <= qr) {
			lz[v] += x;
			push(v, l, r);
			return;
		}
		int mid = (l + r) / 2;
		upd(v * 2 + 0, l, mid, ql, qr, x);
		upd(v * 2 + 1, mid + 1, r, ql, qr, x);
		vmn[v] = min(vmn[v * 2 + 0], vmn[v * 2 + 1]);
		vmx[v] = max(vmx[v * 2 + 0], vmx[v * 2 + 1]);
	}
	int getmin(int v, int l, int r, int ql, int qr) {
		push(v, l, r);
		if (qr < l || r < ql) return (int)(1e18);
		if (ql <= l && r <= qr) return vmn[v];
		int mid = (l + r) / 2;
		return min(getmin(v * 2 + 0, l, mid, ql, qr), getmin(v * 2 + 1, mid + 1, r, ql, qr));
	}
	int getmax(int v, int l, int r, int ql, int qr) {
		push(v, l, r);
		if (qr < l || r < ql) return (int)(-1e18);
		if (ql <= l && r <= qr) return vmx[v];
		int mid = (l + r) / 2;
		return max(getmax(v * 2 + 0, l, mid, ql, qr), getmax(v * 2 + 1, mid + 1, r, ql, qr));
	}
};

vector<int> pos[N];

int sequence(int n, vector<int> a) {
	vector<int> vals = a;
	sort(begin(vals), end(vals));
	int m1 = vals[(n - 1) / 2];
	int m2 = vals[n - 1 - (n - 1) / 2];
	int cnt_m1 = 0, cnt_m2 = 0;
	for (int x : a)
		if (x == m1) cnt_m1++;
		else if (x == m2) cnt_m2++;
	int ans = max(cnt_m1, cnt_m2);
	for (int i = 0; i < n; i++)
		pos[a[i]].push_back(i + 1);
	segtree seg;
	seg = segtree(n + 1);
	for (int i = 1; i <= n; i++)
		seg.upd(1, 0, n, i, n, 1);
	for (int i = 1; i < m1; i++) {
		for (int j : pos[i])
			seg.upd(1, 0, n, j, n, -2);
		int m = (int) pos[i].size();
		vector<int> pmax(m), pmin(m);
		for (int j = 0; j < m; j++) {
			pmax[j] = seg.getmax(1, 0, n, 0, pos[i][j] - 1);
			pmin[j] = seg.getmin(1, 0, n, pos[i][j], n);
		}
		for (int j = 0; j < m; j++)
			ans = max(ans, (int) (upper_bound(begin(pmin), end(pmin), pmax[j]) - begin(pmin) - j));
	}
	seg = segtree(n + 1);
	for (int i = 1; i <= n; i++)
		seg.upd(1, 0, n, i, n, -1);
	for (int i = n; i > m2; i--) {
		for (int j : pos[i])
			seg.upd(1, 0, n, j, n, 2);
		int m = (int) pos[i].size();
		vector<int> pmax(m), pmin(m);
		for (int j = 0; j < m; j++) {
			pmax[j] = -seg.getmin(1, 0, n, 0, pos[i][j] - 1);
			pmin[j] = -seg.getmax(1, 0, n, pos[i][j], n);
		}
		for (int j = 0; j < m; j++)
			ans = max(ans, (int) (upper_bound(begin(pmin), end(pmin), pmax[j]) - begin(pmin) - j));
	}
	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