Submission #3442427


Source Code Expand

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 5;
ll a[maxn];
ll s[maxn * 10],c[maxn * 10];
ll n;
ll lowbit(ll x)
{
	return x & (-x);
}
ll query(ll x)
{
	ll sum = 0;
	for(;x;sum += c[x],x -= lowbit(x));
	return sum;
}
void update(ll x)
{
	for(;x <= maxn * 2;c[x]++,x += lowbit(x));
}
bool check(ll x)
{
	memset(c,0x00,sizeof(c));
	s[0] = 0;
	for(ll i = 1;i <= n; ++i)
	{
		s[i] = s[i - 1] + (a[i] >= x ? 1 : -1);
	}
	ll sum = 0;
	for(ll i = 0;i <= n; ++i)
	{
		sum += query(s[i] + maxn);
		update(s[i] + maxn);
	}
	return sum >= n * (n + 1) / 4;
}
int main()
{
	cin >> n;
	ll left = 0,right = 0;
	for(ll i = 1;i <= n; ++i)
	{
		scanf("%lld",&a[i]);
		right = max(right,a[i]);
	}
	right++;
	while(left+1<right){
		ll mid = (left+right)>>1;
		if(check(mid)) left = mid;
		else right = mid;
	}
	cout << left << endl;
}

Submission Info

Submission Time
Task D - Median of Medians
User zzar
Language C++14 (GCC 5.4.1)
Score 700
Code Size 926 Byte
Status AC
Exec Time 105 ms
Memory 12544 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:45:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a[i]);
                      ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 3
AC × 19
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt
Case Name Status Exec Time Memory
0_00.txt AC 5 ms 10496 KB
0_01.txt AC 5 ms 10496 KB
0_02.txt AC 5 ms 10496 KB
1_00.txt AC 4 ms 10496 KB
1_01.txt AC 14 ms 10496 KB
1_02.txt AC 13 ms 12544 KB
1_03.txt AC 91 ms 12544 KB
1_04.txt AC 54 ms 12544 KB
1_05.txt AC 54 ms 12544 KB
1_06.txt AC 51 ms 12544 KB
1_07.txt AC 48 ms 12544 KB
1_08.txt AC 105 ms 12544 KB
1_09.txt AC 99 ms 12544 KB
1_10.txt AC 104 ms 12544 KB
1_11.txt AC 97 ms 12544 KB
1_12.txt AC 97 ms 12544 KB
1_13.txt AC 100 ms 12544 KB
1_14.txt AC 94 ms 12544 KB
1_15.txt AC 98 ms 12544 KB