Submission #985911

#	Time	Username	Problem	Language	Result	Execution time	Memory
985911		siewjh	Sequence (APIO23_sequence)	C++17	7 / 100	833 ms	129192 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];
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), *root2 = new node(0, N);
	int ans = 0;
	for (int x = 1; x <= N; x++){
		for (int id : occ[x]) root->update(id, N, -2);
		int sz = occ[x].size();
		for (int l = 0, r = 0; l < sz; l++)
			for (; r < sz; r++){ 
				int mxs = root2->mxq(occ[x][r], N) - root2->mnq(0, occ[x][l] - 1);
				int mns = root->mnq(occ[x][r], N) - root->mxq(0, occ[x][l] - 1);
				int len = r - l + 1;
				if (mns <= 0 && mxs >= 0) ans = max(ans, len);
				else break;
			}
		for (int id : occ[x]) root2->update(id, N, -1);
	}
	return ans;
}

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