C++ and Python Solutions: Binary Search, Grid Lookup, and Range Counting Algorithms

C++ and Python Solutions for Algorithmic Problems

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

bool check(const vector<long long>& a, int k, long long maxs) {
int block = 1;
long long sum = 0;

for (long long x : a) {
if (sum + x > maxs) {
block++;
sum = x;
}
else {
sum += x;
}
}

return block <= k;
}

int main() {
int n, k;

if (!(cin >> n >> k)) {
return 0;
}

vector<long long> a(n);

long long maxval = 0;
long long sumval = 0;

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

maxval = max(maxval, a[i]);
sumval += a[i];
}

long long l = maxval;
long long r = sumval;
long long ans = sumval;

while (l <= r) {
long long mid = l + (r - l) / 2;

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

cout << ans << endl;

return 0;
}

Second Program: Finding the k-th Smallest Right or Upper Coordinate

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

int main() {
int n, k;

if (!(cin >> n >> k)) {
return 0;
}

vector<long long> reql(n);

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

cin >> x1 >> y1 >> x2 >> y2;

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

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

cout << reql[k - 1] << '\n';

return 0;
}

Third Program: Grid Position Lookup in Python

import sys

d = sys.stdin.read().split()

j = 0

t = int(d[j])
j += 1

q = d[j:j + t]
j += t

n, m = int(d[j]), int(d[j + 1])
j += 2

pos = {}

for r in range(n):
row = d[j:j + m]
j += m

for c in range(m):
pos[int(row[c])] = (r, c)

out = []

for x in q:
p = pos.get(int(x))

if p:
out.append(f"{p[0]} {p[1]}")
else:
out.append("-1")

print("\n".join(out))

Fourth Program: Counting Elements in Two Intervals

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

long long cr(const vector<long long>& a, long long L, long long R) {
if (L > R) {
return 0;
}

auto rit = upper_bound(a.begin(), a.end(), R);
auto lit = lower_bound(a.begin(), a.end(), L);

return distance(lit, rit);
}

int main() {
int n, q;

if (!(cin >> n >> q)) {
return 0;
}

vector<long long> a(n);

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

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

while (q--) {
long long l1, r1, l2, r2;

cin >> l1 >> r1 >> l2 >> r2;

long long c1 = cr(a, l1, r1);
long long c2 = cr(a, l2, r2);

long long interl = max(l1, l2);
long long interr = min(r1, r2);

long long cinter = cr(a, interl, interr);

long long ans = c1 + c2 - cinter;

cout << ans << "\n";
}

return 0;
}