C++ Algorithms for Binary Search and Prefix Sums

C++ Competitive Programming Solutions

This document contains several C++ solutions for common algorithmic problems involving prefix sums, binary search, and matrix manipulation.

1. Prefix Sum and Lower Bound Algorithm

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    long long k;

    cin >> n >> k;

    vector<long long> pref(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        pref[i] = pref[i - 1] + x;
    }

    int ans = n;

    for (int i = 0; i < n; i++) {
        auto it = lower_bound(
            pref.begin() + i + 1,
            pref.end(),
            pref[i] + k
        );

        if (it != pref.end()) {
            int j = it - pref.begin();
            ans = min(ans, j - i);
        }
    }

    cout << ans << endl;

    return 0;
}

2. Binary Search on Answer

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

bool check(const vector<long long>& a, int k, long long max_sum) {
    int blocks = 1;
    long long current_sum = 0;

    for (long long x : a) {
        if (current_sum + x > max_sum) {
            blocks++;
            current_sum = x;
        } else {
            current_sum += x;
        }
    }

    return blocks <= k;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    if (!(cin >> n >> k))
        return 0;

    vector<long long> a(n);

    long long max_val = 0;
    long long sum_val = 0;

    for (int i = 0; i < n; ++i) {
        cin >> a[i];

        max_val = max(max_val, a[i]);
        sum_val += a[i];
    }

    long long left = max_val;
    long long right = sum_val;
    long long ans = sum_val;

    while (left <= right) {
        long long mid = left + (right - left) / 2;

        if (check(a, k, mid)) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    cout << ans << "\n";

    return 0;
}

3. Sorting and Finding the K-th Element

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

    vector<long long> val(n);

    for (int i = 0; i < n; i++) {
        long long x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        val[i] = max(x2, y2);
    }

    sort(val.begin(), val.end());

    cout << val[k - 1] << endl;

    return 0;
}

4. Matrix Binary Search Algorithm

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<vector<int>> a;

int findRow(int x) {
    int lo = 0, hi = n - 1;

    while (lo <= hi) {
        int mid = (lo + hi) / 2;

        int mn = min(a[mid][0], a[mid][m - 1]);
        int mx = max(a[mid][0], a[mid][m - 1]);

        if (x < mn)
            lo = mid + 1;
        else if (x > mx)
            hi = mid - 1;
        else
            return mid;
    }

    return -1;
}

int findCol(int row, int x) {
    int lo = 0, hi = m - 1;

    bool increasing = (row % 2 == 1);

    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        int v = a[row][mid];

        if (v == x)
            return mid;

        if (increasing) {
            if (v < x)
                lo = mid + 1;
            else
                hi = mid - 1;
        } else {
            if (v > x)
                lo = mid + 1;
            else
                hi = mid - 1;
        }
    }

    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;

    vector<int> q(t);

    for (int i = 0; i < t; i++)
        cin >> q[i];

    cin >> n >> m;

    a.assign(n, vector<int>(m));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    for (int i = 0; i < t; i++) {
        int row = findRow(q[i]);

        int col = (row == -1) ? -1 : findCol(row, q[i]);

        if (col == -1)
            cout << -1 << "\n";
        else
            cout << row << " " << col << "\n";
    }

    return 0;
}