Submission #985867

#	Time	Username	Problem	Language	Result	Execution time	Memory
985867		siewjh	Sequence (APIO23_sequence)	C++17	60 / 100	802 ms	191748 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;

struct node{
	int s, e, m, mn, mx, lazy;
	node *l, *r;
	node (int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1; mn = s, mx = e, lazy = 0;
		if (s != e){
			l = new node(s, m);
			r = new node(m + 1, e);
		}
	}
	void update(int x, int y, int v){
		if (x == s && y == e){
			mn += v; mx += v; lazy += v;
			return;
		}
		else if (y <= m) l->update(x, y, v);
		else if (x > m) r->update(x, y, v);
		else{
			l->update(x, m, v); r->update(m + 1, y, v);
		}
		mn = min(l->mn, r->mn) + lazy;
		mx = max(l->mx, r->mx) + lazy;
	}
	int mnq(int x, int y){
		if (x == s && y == e) return mn;
		else if (y <= m) return l->mnq(x, y) + lazy;
		else if (x > m) return r->mnq(x, y) + lazy;
		else return min(l->mnq(x, m), r->mnq(m + 1, y)) + lazy;
	}
	int mxq(int x, int y){
		if (x == s && y == e) return mx;
		else if (y <= m) return l->mxq(x, y) + lazy;
		else if (x > m) return r->mxq(x, y) + lazy;
		else return max(l->mxq(x, m), r->mxq(m + 1, y)) + lazy;
	}
};

vector<int> occ[MAXN];
vector<int> mnlq[MAXN], mxlq[MAXN], mnrq[MAXN], mxrq[MAXN];
int sequence(int N, vector<int> A){
	for (int i = 1; i <= N; i++) occ[A[i - 1]].push_back(i);
	node *root = new node(0, N);
	for (int x = 1; x <= N; x++){
		for (int id : occ[x]) root->update(id, N, -1);
		int sz = occ[x].size();
		for (int i = 0; i < sz; i++){
			mnlq[x].push_back(root->mnq(0, occ[x][i] - 1));
			mxlq[x].push_back(root->mxq(0, occ[x][i] - 1));
			mnrq[x].push_back(root->mnq(occ[x][i], N));
			mxrq[x].push_back(root->mxq(occ[x][i], N));
		}
		for (int id : occ[x]) root->update(id, N, -1);
	}
	int l = 1, r = N, ans = 1;
	while (l <= r){
		int m = (l + r) >> 1;
		bool ok = 0;
		for (int x = 1; x <= N; x++){
			int sz = occ[x].size();
			for (int l = 0, r = m - 1; r < sz; l++, r++)
				if (mnrq[x][r] - mxlq[x][l] <= m && mxrq[x][r] - mnlq[x][l] >= -m)
					ok = 1;
		}
		if (ok){
			ans = m; l = m + 1;
		}
		else r = m - 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: 0 / 22
• Subtask 7: 0 / 18