GUuJsY - Online C++ Compiler & Debugging Tool

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

int left_part_last_index(long long target, const vector<long long>& arr, int n) {
	int low = 1;      // Start at 1 to skip arr[0] sentinel
	int high = n;     // End at n to skip arr[n+1] sentinel
	int answer = 0;   // Initialize default value (0 elements <= target)

	while(low <= high) {
		int mid = low + (high - low) / 2; // Fixed precedence bug: (low + high) / 2

		if(arr[mid] <= target) {
			answer = mid;   // Store valid candidate index
			low = mid + 1;  // Look for a larger valid index on the right
		} else {
			high = mid - 1; // Element too large, search left
		}
	}
	return answer;
}

int main() {
	int n;
	if (!(cin >> n)) return 0;

	// arr size is n+2 to safely hold INT_MIN at 0 and INT_MAX at n+1
	vector<long long> arr(n+2);
	vector<long long> prefix(n+1, 0); // Changed to long long to prevent overflow

	// Fixed: Store elements from index 1 to n (leaving 0 and n+1 for sentinels)
	for(int i = 1; i <= n; i++) {
		cin >> arr[i];
	}

	// Fixed: Set sentinels AFTER taking inputs so they aren't overwritten
	arr[0] = LLONG_MIN;
	arr[n+1] = LLONG_MAX;

	// Fixed: Sort ONLY the elements from index 1 to n
	sort(arr.begin() + 1, arr.begin() + n + 1);

	// Fixed: Compute prefix sums AFTER sorting (and correctly handling prefix[0] = 0)
	long long sum = 0;
	for(int i = 1; i <= n; i++) {
		sum += arr[i];
		prefix[i] = prefix[i-1] + arr[i]; // No more negative indexing (prefix[0] exists)
	}

	int q;
	cin >> q;

	for(int i = 0; i < q; i++) {
		long long target;
		cin >> target;

		// li represents the number of elements <= target (from index 1 to li)
		long long li = left_part_last_index(target, arr, n);

		long long left_part = target * li - (prefix[li]); // O(1)
		long long right_part = (sum - prefix[li]) - target * (n - li); // O(1)

		long long min_operations = left_part + right_part;

		cout << "Minimum operations for target " << target << " is : " << min_operations << endl;
	}
	return 0;
}