Binary Search to Maximize Value in C++

This C++ code snippet uses binary search to find the maximum value that satisfies certain conditions based on given inputs. It reads multiple test cases and processes an array to determine the optimal result. The approach is optimized for performance, handling large input sizes efficiently.

#include <cstdio>
#include <algorithm>

using namespace std;

int n, k, a[500009], o;
int sp[500009];

bool gt(int x) {
    for (int i = 0; i <= o; i++)
        sp[i] = 0;
    for (int i = 1; i <= n; i++) {
        int p = i % k == 0 ? k : i % k;
        sp[p] = max(sp[p], sp[p - 1] + (a[i] >= x));
    }
    int p = n % k == 0 ? k : n % k;
    return sp[p] * 2 > o;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &n, &k);
        o = n;
        while (o > k)
            o -= k;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        int l = 1, r = 1e9 + 7;
        while (l + 1 < r) {
            int mid = (l + r) >> 1;
            if (gt(mid))
                l = mid;
            else
                r = mid;
        }
        printf("%d\n", l);
    }
    return 0;
}

Editor is loading...