oj.uz

Submission #750273

# Submission time Handle Problem Language Result Execution time Memory
750273 2023-05-29T09:01:46 Z 1ne Sequence (APIO23_sequence) C++17
0 / 100
 2000 ms 120912 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 275 ms 115228 KB Output is correct
3 Incorrect 269 ms 115120 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 232 ms 108392 KB Output is correct
3 Correct 1337 ms 109420 KB Output is correct
4 Correct 232 ms 109376 KB Output is correct
5 Correct 235 ms 108368 KB Output is correct
6 Execution timed out 2070 ms 109552 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 120900 KB Output is correct
2 Correct 333 ms 120912 KB Output is correct
3 Incorrect 406 ms 120252 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -