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 |
|
|
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 |