Submission #1009783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009783		pcc	Sequence (APIO23_sequence)	C++17	100 / 100	630 ms	62296 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;
vector<int> pos[mxn];
int N,ans,arr[mxn];

struct SEG{
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
	struct node{
		int mx,mn,tag;
		node(){
			mx = mn = tag = 0;
		}
	};
	node seg[mxn*4];
	void modify(int now,int l,int r,int s,int e,int v){
		if(l>=s&&e>=r){
			seg[now].tag += v;
			return;
		}
		if(mid>=s)modify(ls,l,mid,s,e,v);
		if(mid<e)modify(rs,mid+1,r,s,e,v);
		seg[now].mx = max(seg[ls].mx+seg[ls].tag,seg[rs].mx+seg[rs].tag);
		seg[now].mn = min(seg[ls].mn+seg[ls].tag,seg[rs].mn+seg[rs].tag);
		return;
	}
	int getmn(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return seg[now].mn+seg[now].tag;
		if(mid>=e)return getmn(ls,l,mid,s,e)+seg[now].tag;
		else if(mid<s)return getmn(rs,mid+1,r,s,e)+seg[now].tag;
		else return min(getmn(ls,l,mid,s,e),getmn(rs,mid+1,r,s,e))+seg[now].tag;
	}
	int getmx(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return seg[now].mx+seg[now].tag;
		if(mid>=e)return getmx(ls,l,mid,s,e)+seg[now].tag;
		else if(mid<s)return getmx(rs,mid+1,r,s,e)+seg[now].tag;
		else return max(getmx(ls,l,mid,s,e),getmx(rs,mid+1,r,s,e))+seg[now].tag;
	}
#undef ls
#undef rs
#undef mid
};
SEG seg;

bool intersect(pii a,pii b){
	if(a.fs==b.fs)return true;
	if(a.fs>b.fs)swap(a,b);
	return a.sc>=b.fs;
}

void calc(vector<int> v){
	if(v.empty())return;
	for(int i = 0;i<v.size();i++){
		seg.modify(0,0,N,v[i],N,-1);
	}
	v.insert(v.begin(),0);
	v.push_back(N+1);
	vector<pii> rng;
	for(int i = 1;i<v.size();i++)rng.push_back(pii(seg.getmn(0,0,N,v[i-1],v[i]-1),seg.getmx(0,0,N,v[i-1],v[i]-1)));
	auto pref = rng;
	for(int i = 1;i<pref.size();i++){
		pref[i].fs = min(pref[i].fs,pref[i-1].fs);
		pref[i].sc = max(pref[i].sc,pref[i-1].sc);
	}

	auto check = [&](int dis){
		pii pre = pii(0,0);
		for(int i = dis;i<rng.size();i++){
			auto ta = rng[i-dis];
			ta.fs = min(ta.fs,pre.fs);
			ta.sc = max(ta.sc,pre.sc);
			auto tb = rng[i];
			tb.fs -= dis,tb.sc += dis;
			if(intersect(ta,tb))return true;
			pre = ta;
			pre.fs--;pre.sc++;
		}
		return false;
	};
	int l = 0,r = rng.size()-1;
	/*
	for(int i = l;i<=r;i++){
		if(check(i))ans = max(ans,i);
	}
	*/
	while(l != r){
		int mid = (l+r+1)>>1;
		if(check(mid))l = mid;
		else r = mid-1;
	}

	ans = max(ans,l);
	for(int i = 1;i+1<v.size();i++){
		seg.modify(0,0,N,v[i],N,-1);
	}
	return;
}

namespace BRUTE{
	ordered_set<pii> st;
	int cnt[mxn];
	void check(int head){
		st.clear();
		memset(cnt,0,sizeof(cnt));
		for(int i = head;i<=N;i++){
			cnt[arr[i]]++;
			st.insert(pii(arr[i],i));
			int tl = (st.size()-1)>>1,tr = st.size()>>1;
			int val = st.find_by_order(tl)->fs;
			ans = max(ans,cnt[val]);
			val = st.find_by_order(tr)->fs;
			ans = max(ans,cnt[val]);
		}
		return;
	}
	int GO(){
		ans = 0;
		for(int i = 1;i<=N;i++)check(i);
		return ans;
	}
}

int32_t sequence(int32_t NN, std::vector<int32_t> AA) {
	N = NN;
	for(int i = 0;i<N;i++)arr[i+1] = AA[i],pos[AA[i]].push_back(i+1);
	//int t1 = BRUTE::GO();
	for(int i = 1;i<=N;i++)seg.modify(0,0,N,i,i,i);
	ans = 0;
	for(int i = 1;i<mxn;i++)calc(pos[i]);
	//assert(ans == t1);
	return ans;
}

Compilation message (stderr)

sequence.cpp: In function 'void calc(std::vector<int>)':
sequence.cpp:71:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for(int i = 0;i<v.size();i++){
      |                ~^~~~~~~~~
sequence.cpp:77:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for(int i = 1;i<v.size();i++)rng.push_back(pii(seg.getmn(0,0,N,v[i-1],v[i]-1),seg.getmx(0,0,N,v[i-1],v[i]-1)));
      |                ~^~~~~~~~~
sequence.cpp:79:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for(int i = 1;i<pref.size();i++){
      |                ~^~~~~~~~~~~~
sequence.cpp: In lambda function:
sequence.cpp:86:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   for(int i = dis;i<rng.size();i++){
      |                   ~^~~~~~~~~~~
sequence.cpp: In function 'void calc(std::vector<int>)':
sequence.cpp:111:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |  for(int i = 1;i+1<v.size();i++){
      |                ~~~^~~~~~~~~

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