Submission #1050923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050923		vjudge1	Sequence (APIO23_sequence)	C++17	35 / 100	549 ms	44688 KiB

sequence

#include "sequence.h"

#include <bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> st;

int sequence(int n, std::vector<int> A) {
	map<int,int> mp;
	if(n <= 2000){
		int ans = 0;
		for(int i = 0;i < n;i++){
			mp.clear();
			st.clear();
			for(int j = i;j < n;j++){
				st.insert(A[j]);
				mp[A[j]]++;
				int a = *st.find_by_order((j - i) / 2), b = *st.find_by_order((j - i + 1) / 2);
				ans = max({ans, mp[a], mp[b]});
			}
		}
		return ans;
	}
	int ans = 0;
	vector<int> B = A;
	sort(B.begin(), B.end());
	int d = n;
	int c = B[(n - 1) / 2];
	for(int i = 1;i < n;i++){
		if(A[i] < A[i - 1]){
			d = i;
			break;
		}
	}
	map<int,int> mp1, mp2;
	for(int i = 0;i < d;i++)mp1[A[i]]++;
	for(int i = d;i < n;i++)mp2[A[i]]++;
	for(auto [i, j]: mp1)ans = max(ans, j);
	for(auto [i ,j]: mp2)ans = max(ans, j);
	for(int i = 0;i < n;i++){
		if(A[i] >= c)ans = max(ans, mp1[A[i]] + mp2[A[i]]);
	}
	return ans;
}

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