Submission #3104934

Source Code Expand

Copy
```#include <bits/stdc++.h>
#define pb push_back
#define REP(i, n) for (signed long long i = 0; i < (n); i++)
#define MOD 998244353
#define bitcnt(a) (ll) __builtin_popcount((a))
#define lb(a, b) lower_bound((a).begin(), (a).end(), (b))
#define ub(a, b) upper_bound((a).begin(), (a).end(), (b))
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<string, string> PS;

template <class T>
struct BIT {
vector<T> x;
BIT(int n) : x(n, 0) {
// initialize
}

T sum(int i, int j) {
if (i == 0) {
T S = 0;
for (j; j >= 0; j = (j & (j + 1)) - 1)
S += x[j];
return S;
} else
return sum(0, j) - sum(0, i - 1);
}
void add(int k, T a) {
for (; k < x.size(); k |= k + 1)
x[k] += a;
}
};

int main() {
ll n;
cin >> n;
vector<ll> v;
REP(i, n) {
ll h;
cin >> h;
v.pb(h);
}
vector<ll> s = v;

sort(s.begin(), s.end());
s.erase(unique(s.begin(), s.end()), s.end());

ll ok = 0, ng = s.size();

while (ng - ok > 1) {
ll m = s[(ok + ng) / 2];
vector<ll> imos;
for (auto &a : v) {
if (a < m) {
imos.pb(-1);
} else {
imos.pb(1);
}
}

REP(i, imos.size() - 1) {
imos[i + 1] += imos[i];
}
BIT<ll> b(2 * n + 1);

ll cnt = 0;
REP(i, n) {
cnt += (i - b.sum(0, imos[i] + n)) + (v[i] < m);
}
if (cnt < (n + (n * (n - 1)) / 2) / 2) {
ok = (ok + ng) / 2;
} else {
ng = (ok + ng) / 2;
}
}
cout << s[ok] << endl;
}```

#### Submission Info

Submission Time 2018-08-31 03:55:46+0900 D - Median of Medians keidaroo C++14 (GCC 5.4.1) 0 1625 Byte WA 118 ms 5240 KB

#### Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 0_00.txt, 0_01.txt, 0_02.txt
All 0 / 700 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 1 ms 256 KB
0_01.txt 1 ms 256 KB
0_02.txt 1 ms 256 KB
1_00.txt 1 ms 256 KB
1_01.txt 1 ms 256 KB
1_02.txt 19 ms 1908 KB
1_03.txt 46 ms 1908 KB
1_04.txt 88 ms 5240 KB
1_05.txt 90 ms 5240 KB
1_06.txt 89 ms 5240 KB
1_07.txt 92 ms 5240 KB
1_08.txt 117 ms 5176 KB
1_09.txt 117 ms 5204 KB
1_10.txt 116 ms 5108 KB
1_11.txt 117 ms 5108 KB
1_12.txt 113 ms 5080 KB
1_13.txt 118 ms 5224 KB
1_14.txt 113 ms 5176 KB
1_15.txt 113 ms 5212 KB