http://poj.org/problem?id=3685
A_ij = i * i + 100,000 * i + j * j - 100,000 * j + i * j
で定義されるN次正方行列のM番目の値を調べる。
ある値x未満の数が行列中に何個あるかは A_ijの値はjを固定したときiについて単調増加なので各列について二分探索をすればN * lg(N)で求められる。
x未満の数がM個未満となるような最大のxをとってくればそれが中央値。
1 #include <iostream>
2
3 using namespace std;
4
5 typedef long long ll;
6
7 ll N, M;
8
9 ll count_lt(ll x) {
10 ll cnt = 0;
11 for (ll j = 1; j <= N; j++) {
12 // [lb, ub)
13 ll lb = 0, ub = N+1;
14 while (lb + 1 < ub) {
15 ll i = (lb + ub) / 2; // mid = i
16 if (i * i + 100000 * i + j * j - 100000 * j + i * j < x) {
17 lb = i;
18 } else {
19 ub = i;
20 }
21 }
22 cnt += lb;
23 }
24 return cnt;
25 }
26
27 int main() {
28 int T; // the number of test cases
29 cin >> T;
30 while (T--) {
31 cin >> N >> M;
32 ll lb = -1LL << 60, ub = 1LL << 60;
33 while (lb + 1 < ub) {
34 ll mid = (lb + ub) / 2;
35 if (count_lt(mid) < M) {
36 lb = mid;
37 } else {
38 ub = mid;
39 }
40 }
41 cout << lb << endl;
42 }
43 return 0;
44 }