Submission #3098603

---

Source Code Expand

#include <iostream>
#include<algorithm>
#include <vector>
#include<cmath>
using namespace std;

int N;
int bit[1000010];
void init(int size){
	
	for(int i = 0; i < size; i++)
	{
		bit[i] = 0;
	}
	
}
void add(int a, int w) {
	for (int x = a; x <= 1000010; x += x & -x) bit[x] += w;
}
int sum(int a) {
	int ret = 0;
	for (int x = a; x > 0; x -= x & -x) ret += bit[x];
	return ret;
}

int main()
{
	int N;
	cin >> N;

	vector<int> A(N);
	vector<int> sorted(N);
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
		sorted[i] = A[i];
	}
	sort(sorted.begin(), sorted.end());

	vector<int> S(N);

	int lb =0, ub = N;
	while(ub - lb > 1){
		// cout << "ub=" << ub <<"lb=" << lb << endl;

		init(2*N+1);
		// cout << "------" << endl;
		int len = ub-lb;
		int x = len/2;
		int median = sorted[x+lb];
		// cout << "median:" << median << endl;
		for (int i = 0; i < N; i++)
		{
			if (median <= A[i])
			{
				S[i] = 1;
			}
			else
			{
				S[i] = -1;
			}
		}
		for (int i = 0; i < N; i++)
		{
			if (i != 0)
			{
				S[i] = S[i - 1] + S[i];
			}
			else
			{
				S[0] = S[0];
			}
		}
		
		// add(N,1);
		int cnt = 0;
		for(int i = 0; i < N; i++)
		{
			cnt += sum(S[i]+N);
			// cout << "sum("<<S[i]+N<<")="<<sum(S[i]+N)<<endl;
			add(S[i]+N,1);

		}
		// cout << "cnt=" << cnt << endl;
		if(cnt>=ceil(N*(N+1)/2/2)){
			lb = x+1;
		}else{
			ub = x-1;
		}
		// break;
	}
	cout << sorted[lb] << endl;
	return 0;
}

Submission Info

Judge Result