Submission #1168597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168597		rayan_bd	Sequence (APIO23_sequence)	C++20	28 / 100	2095 ms	31920 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

const double INF = 5e18;
const int mxN = 5e5+100;

#define fi first
#define se second
#define all(v) v.begin(), v.end()

int seg[mxN*4];

void update(int node,int start,int end,int idx,int val,bool fix){
	if(start==end){
		if(fix) seg[node]=val;
		else seg[node]+=val;
		return;
	}
	int mid=start+(end-start)/2;
	if(idx<=mid) update(node*2+1,start,mid,idx,val,fix);
	else update(node*2+2,mid+1,end,idx,val,fix);
	seg[node]=seg[node*2+1]+seg[node*2+2];
}

int qry(int node,int start,int end,int l,int r){
	if(start>r||end<l) return 0ll;
	if(start>=l&&end<=r) return seg[node];
	int mid=start+(end-start)/2;
	return qry(node*2+1,start,mid,l,r)+qry(node*2+2,mid+1,end,l,r);
}

int n;

int find_val(int pos){
	int st=1,en=n,ans=1;
	while(st<=en){
		int mid=st+(en-st)/2;
		if(qry(0,1,n,1,mid)>=pos){
			ans=mid;
			en=mid-1;
		}else{
			st=mid+1;
		}
	}
	return ans;
}

int sequence(int N,vector<int> A){
	n=N;
	int ans=1;
	for(int i=0;i<N;++i){
		map<int,int> mp;
		for(int j=i;j<N;++j){
			++mp[A[j]];
			update(0,1,n,A[j],1,0);
			if((j-i+1)&1){
				ans=max(ans,mp[find_val((j-i+2)/2)]);
			}else{
				ans=max(ans,mp[find_val((j-i+1)/2)]);
				ans=max(ans,mp[find_val((j-i+1)/2+1)]);
			}
		}
		for(int j=i;j<N;++j) update(0,1,N,A[j],0,1);
	}
	for(auto it:A) update(0,1,N,it,0,1);
	return ans;
}

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