Submission #881662

#	Time	Username	Problem	Language	Result	Execution time	Memory
881662		tsumondai	Sequence (APIO23_sequence)	C++17	100 / 100	883 ms	170008 KiB

sequence

/*
给定序列n。 调用 res 来计算 x 在段 l,r 中出现的次数（x 是段 l,r 中的中位数 - 可以有 2 个中位数）。 求任意线段 l,r 的最大分辨率。
Given sequence n. Call res the number of times x appears in segment l,r, (x is the median number in segment l,r - there can be 2 medians). Find the maximum res for any segment l,r.
Cho dãy n. Gọi res số số lần xuất hiện của x trong đoạn l,r, (x là số median trong đoạn l,r - có thể có 2 median). Tìm res lớn nhất với đoạn l,r bất kì.
*/
#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
 
struct node {
	int mi, mx, lazy;
 
	node(): mi(0), mx(0), lazy(0) {};
 
	node(int _mi, int _mx): mi(_mi), mx(_mx), lazy(0) {};
};
 
const int maxn = 5e5 + 20;
int a[maxn];
vector<int> pos[maxn];
vector<int> pref[maxn][2];
vector<int> suf[maxn][2];
node tree[maxn * 4];
int n;
 
node merge(node L, node R) {
	return node(min(L.mi, R.mi), max(L.mx, R.mx));
}
 
void build(int id, int lt, int rt) {
	if (lt == rt) {
		tree[id] = node(lt, lt);
		return;
	}
	int mt = (lt + rt) / 2;
	build(id * 2, lt, mt);
	build(id * 2 + 1, mt + 1, rt);
	tree[id] = merge(tree[id * 2], tree[id * 2 + 1]);
}
 
void push(int id) {
	tree[id * 2].lazy += tree[id].lazy;
	tree[id * 2].mi += tree[id].lazy;
	tree[id * 2].mx += tree[id].lazy;
	tree[id * 2 + 1].lazy += tree[id].lazy;
	tree[id * 2 + 1].mi += tree[id].lazy;
	tree[id * 2 + 1].mx += tree[id].lazy;
	tree[id].lazy = 0;
}
 
 
void update(int id, int lt, int rt, int ql, int qr) {
	if (lt == ql && rt == qr) {
		tree[id].lazy -= 2;
		tree[id].mi -= 2;
		tree[id].mx -= 2;
		return;
	}
	push(id);
	int mt = (lt + rt) / 2;
	if (qr <= mt) {
		update(id * 2, lt, mt, ql, qr);
	}
	else if (ql >= mt + 1) {
		update(id * 2 + 1, mt + 1, rt, ql, qr);
	}
	else {
		update(id * 2, lt, mt, ql, mt);
		update(id * 2 + 1, mt + 1, rt, mt + 1, qr);
	}
	tree[id] = merge(tree[id * 2], tree[id * 2 + 1]);
}
 
node get(int id, int lt, int rt, int ql, int qr) {
	if (lt == ql && rt == qr) {
		return tree[id];
	}
	push(id);
	int mt = (lt + rt) / 2;
	if (qr <= mt) {
		return get(id * 2, lt, mt, ql, qr);
	}
	else if (ql >= mt + 1) {
		return get(id * 2 + 1, mt + 1, rt, ql, qr);
	}
	else {
		return merge(get(id * 2, lt, mt, ql, mt), get(id * 2 + 1, mt + 1, rt, mt + 1, qr));
	}
}
 
bool check(int k) {
	for (int i = 1; i <= n; i++) {
		for (int j = k - 1; j < (int)pos[i].size(); j++) {
			if (suf[i][0][j] >= pref[i][0][j - (k - 1)] && suf[i][1][j] <= pref[i][1][j - (k - 1)]) {
				return true;
			}
		}
	}
	return false;
}
 
int sequence(int _N, vector<int> _A) {
	n = _N;
	for (int i = 1; i <= n; i++) {
		a[i] = _A[i - 1];
	}
	for (int i = 1; i <= n; i++) {
		pos[a[i]].push_back(i);
	}
	build(1, 0, n);
	for (int i = 1; i <= n; i++) {
		for (auto p: pos[i]) {
			pref[i][0].push_back(get(1, 0, n, 0, p - 1).mi);
			suf[i][0].push_back(get(1, 0, n, p, n).mx);
		}
		for (auto p: pos[i]) {
			update(1, 0, n, p, n);
		}
		for (auto p: pos[i]) {
			pref[i][1].push_back(get(1, 0, n, 0, p - 1).mx);
			suf[i][1].push_back(get(1, 0, n, p, n).mi);
		}
	}
	int res = 1;
	int lt = 1;
	int rt = n;
	while (lt <= rt) {
		int mt = (lt + rt) / 2;
		if (check(mt)) {
			res = mt;
			lt = mt + 1;
		}
		else {
			rt = mt - 1;
		}
	}
	return res;
}

• 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