# Positive Segments

I'm trying to solve the following question:

You have an array A of size n, containing −1 or 1 only, and s segments (not necessarily different). Each segment is defined by 2 integers li and ri (1 ≤ li ≤ ri ≤ n) and represent the subarray Ali, Ali +1 , ..., Ari of the array A.

A segment [li, ri] is called positive if the sum of elements in the subarray is strictly greater than 0. That is Ali, Ali +1 , ..., Ari ≥0. Forexample,ifA=[−1,−1,1,−1,1],thenthesegments[3,5]and[5,5] are positive (sum of elements is greater than 0), but the segments [1, 2] or [1, 5] are not positive.

Now you have q queries. In each query, you are given an integer j (1 ≤ j ≤ n) such that you set Aj = |Aj| (Absolute value of Aj). You have to find the minimum number of queries after which at least k (≤ s) of given segments become positive or tell it is impossible.

Note: It might happen that there already exists k positive segments.

Input First line of input consists of number of test cases t. Every test case is defined as follows- – First line contains 2 integer n and s. – Next line contains n integers where ith integer denotes Ai. – Following s lines contain 2 integers li and ri defining ith segment. – Next line contains 2 integers q and k. – Next line contains q integers where ith integer denotes x corresponding to ith query.

Output For each test case, output a line containing the minimum number of queries needed for that case. If it is impossible in all the queries then output -1 in that case.

There is an additional criteria to just use three libraries, i.e., iostream, vector & cstdlib.

My code for the same is:

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

int countPositiveSegments(vector<int>& A, vector<vector<int>>& sets) {
int count = 0;
for (const vector<int>& segment : sets) {
int sum = 0;
for (int i = segment[0] - 1; i < segment[1]; i++) {
sum += A[i];
}
if (sum > 0) {
count++;
}
}
return count;
}

int main() {
int total_cases;
cin >> total_cases;
while (total_cases > 0) {
int n, s, q, k;
cin >> n >> s;
vector<int> A;
vector<vector<int>> sets;
while (n > 0) {
int temp;
cin >> temp;
A.push_back(temp);
n--;
}
while (s > 0) {
int temp1, temp2;
vector<int> temp3;
cin >> temp1 >> temp2;
temp3.push_back(temp1);
temp3.push_back(temp2);
sets.push_back(temp3);
s--;
}
cin >> q >> k;
vector<int> queries;
while (q > 0) {
int temp;
cin >> temp;
queries.push_back(temp);
q--;
}

// Initialize variables
int queries_needed = -1;
int total_positive_sets = countPositiveSegments(A, sets);

if (total_positive_sets < k) {
// If there are not enough positive sets, then iterate through queries
for (int i = 0; i < queries.size(); i++) {
int x = queries[i] - 1; // Adjust the 0-based index
A[x] = abs(A[x]);
int new_positive_sets = countPositiveSegments(A, sets);

if (new_positive_sets >= k) {
queries_needed = i + 1;
break;
}
}
}

if (queries_needed != -1) {
cout << queries_needed << endl;
} else {
cout << -1 << endl;
}

total_cases--;
}
return 0;
}


It works perfectly fine for:

Input (stdin)
2
5 2
-1 -1 1 -1 -1
1 2
2 5
6 1
3 1 1 2 5 3
5 3
-1 -1 -1 -1 -1
1 3
2 2
1 1
3 2
2 4 5

4
-1

Expected Output
4
-1


For a few of the hidden test cases, it provides a Time Limit Exceeded error. I'm trying to ascertain a new way which can solve the problem.

Algorithmic deficiencies.

• countPositiveSegments has a time complexity proportional to the combined size of all segments, which can grow quadratically with the size of array. And you do it for every query. I am not surprised at all that the solution times out.

You can count initial positive segments much faster by computing a accumulated sum of the array, acc[i] = acc[i-1] + A[i]) (in $$\O(n)\$$ time); then the segment is positive if acc[ri] > acc[li] (in $$\O(s)\$$ time).

• You don't need to recount positive segments when A[x] is 1. Fix is trivial.

• Once a segment becomes positive, you don't need to account for it anymore. Just forget that it existed.

• If A[x] is -1, only the segments containing x are affected; you don't need to bother about the rest. The fix is less trivial: you need more elaborate data structure. A segment tree perhaps?

Code review.

• using namespace std; is a very bad habit.

• temp, temp1, temp2, temp3 are not the greatest names. If you don't know how to name a variable, think twice: do you really need it?

• More functions, please. Every loop implements an important operation, and therefore deserves a name, like get_array, get_segments, etc.

• I don't see the need for vector<int> queries. It is a waste of space. You should process queries one by one.

• if (total_positive_sets < k) does not need to be special cased. In fact, doing so results in the bug: if this condition is initially false, the loop is not entered, and queries_needed remains -1, even though you already have enough positive segments. A natural way to write the loop is

  while ((total_positive_sets < k) && (queries < q))

• vector<int> temp3 does not deserve to be a vector. It is a pair<int, int>.

• If you read the question again, it is mentioned only three libraries are allowed so pair can't be implemented Sep 12, 2023 at 5:00
• Instead of std::pair<int, int> just create a struct segment { int li; int ri; }. Then std::vector<segment> sets; … sets.emplace_back(temp1, temp2); Sep 12, 2023 at 10:16