Submission #1009474

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009474		pcc	Sequence (APIO23_sequence)	C++17	40 / 100	2077 ms	52848 KiB

sequence

#include "sequence.h"

#include <vector>
#include <bits/stdc++.h>
#include <bits/extc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")
using namespace std;
using namespace __gnu_pbds;

#define pii pair<int,int>
#define fs first
#define sc second

template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

const int mxn = 5e5+10;
int cnt[mxn],arr[mxn];
int N,ans;
vector<pii> v;
set<int> st;

struct BIT{
	const static int LEN = 2e6+10;
	int bit[LEN];
	BIT(){}
	void init(){
		fill(bit,bit+LEN,LEN);
	}
	void modify(int p,int v){
		assert(p>0&&p<LEN);
		for(;p<LEN;p+=p&-p)bit[p] = min(bit[p],v);
	}
	int getval(int p){
		int re = LEN;
		assert(p>0&&p<LEN);
		for(;p>0;p-= p&-p)re = min(re,bit[p]);
		return re;
	}
};

namespace CHECK{
	BIT bit;
	int P[mxn],Q[mxn];
	int lp[mxn];
	void CALC(int tar){
		fill(lp,lp+mxn,mxn);
		for(int i = 1;i<=N;i++){
			P[i] = P[i-1],Q[i] = Q[i-1];
			if(arr[i]>tar)P[i]++;
			else if(arr[i]<tar)P[i]--;
			else if(arr[i] == tar)Q[i]++;
		}
		vector<pii> v;
		for(int i = 0;i<=N;i++){
			v.push_back(pii(P[i],i));
		}
		sort(v.begin(),v.end());
		bit.init();
		for(auto [_,now] : v){
			int d = Q[now]-P[now]+mxn;
			lp[now] = min(lp[now],bit.getval(d));
			bit.modify(d,now);
		}
		reverse(v.begin(),v.end());
		bit.init();
		for(auto [_,now] : v){
			int d = P[now]+Q[now]+mxn;
			lp[now] = min(lp[now],bit.getval(d));
			bit.modify(d,now);
		}
		for(int i = 1;i<=N;i++){
			int tl = lp[i];
			if(tl<i)ans = max(ans,Q[i]-Q[tl]);
		}
		return;
	}
}

int sequence(int NN, std::vector<int> AA) {
	N = NN;
	for(int i = 0;i<N;i++)arr[i+1] = AA[i],st.insert(AA[i]);
	ans = 0;
	for(auto &i:st)CHECK::CALC(i);
	return ans;
}

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