Submission #750273

#	Time	Username	Problem	Language	Result	Execution time	Memory
750273		1ne	Sequence (APIO23_sequence)	C++17	0 / 100	2070 ms	120912 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
struct dataa{
	vector<int>v;
};
struct MTree{
	vector<dataa>tree;
	void build(int node,int left,int right,vector<int>&arr,int n){
		if (left == right){
			tree[node].v.push_back(arr[left]);
			return ;
		}
		int mid = (left + right)>>1;
		int z = node + ((mid - left + 1)<<1);
		build(node + 1,left,mid,arr,n);
		build(z,mid + 1,right,arr,n);
		tree[node] = combine(tree[node + 1],tree[z]);
	}
	void init(int n,vector<int>&arr){
		tree.resize(2*n - 1);
		build(0,0,n-1,arr,n);
	}
	dataa combine(dataa left,dataa right){
		dataa res;
		merge(left.v.begin(),left.v.end(),right.v.begin(),right.v.end(),back_inserter(res.v));
		return res;
	}
	int query(int node,int left,int right,int qleft,int qright,int v){
		if (qright<left|| qleft > right)return 0;
		if (qleft<=left && qright>=right){
			//cout<<left<<" "<<right<<" "<<" "<<v<<" "<<(int)tree[node].v.size() - (upper_bound(tree[node].v.begin(),tree[node].v.end(),v) - tree[node].v.begin())<<'\n';
			return (int)tree[node].v.size() - (upper_bound(tree[node].v.begin(),tree[node].v.end(),v) - tree[node].v.begin());
		}
		int mid = (left + right)>>1;
		int z = node + ((mid - left + 1)<<1);
		return query(node + 1,left,mid,qleft,qright,v) + query(z,mid + 1,right,qleft,qright,v);
	}
	int query2(int node,int left,int right,int qleft,int qright,int v){
		if (qright<left|| qleft > right)return 0;
		if (qleft<=left && qright>=right){
			return lower_bound(tree[node].v.begin(),tree[node].v.end(),v) - tree[node].v.begin();
		}
		int mid = (left + right)>>1;
		int z = node + ((mid - left + 1)<<1);
		return query2(node + 1,left,mid,qleft,qright,v) + query2(z,mid + 1,right,qleft,qright,v);
	}
};
int sequence(int N, std::vector<int> A) {
  MTree st;
  st.init(N,A);
  vector<vector<int>>adj(N);    	
  for (int i = 0;i<N;++i){
  	adj[A[i] - 1].push_back(i);
  }
  int ans = 1;
  int mx = 0;  
  for (int i = 0;i<N;++i){
  	mx = max(mx,(int)adj[i].size());
  }    
  vector<int>order(N);
  iota(order.begin(),order.end(),0);
  sort(order.begin(),order.end(),[&](int i,int j){
     return (int)adj[i].size() > (int)adj[j].size();
  });            
  for (int i = mx;i > 1;--i){
  	for (int j:order){
  		if ((int)adj[j].size() < i){
  			break;		
  		}
  		for (int k = 0;k + i - 1<(int)adj[j].size();++k){
  			int gr = st.query(0,0,N - 1,adj[j][k],adj[j][k + i - 1],j + 1);
  			int ls = st.query2(0,0,N - 1,adj[j][k],adj[j][k + i - 1],j + 1);
  			//cout<<j<<" "<<ls<<" "<<i<<" "<<gr<<" "<<adj[j][k]<<" "<<adj[j][k + i - 1]<<'\n';
  			if ((ls + i + gr) / 2 >= ls && (ls + i + gr) / 2 < ls + i){
  				return i;
  			}
  			if ((ls + i + gr - 1) / 2 >= ls && (ls + i + gr - 1) / 2 < ls + i){
  				return i;
  			}
  		}	
  	}
  }
  return 1;
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:57:7: warning: unused variable 'ans' [-Wunused-variable]
   57 |   int ans = 1;
      |       ^~~

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