0

i was doing some problem in some competitive coding site, it basically ask you to count how many element is greater than min and lower or equal to the max

for example, i have an array {3,6,8,10,20} and the min is 2 and the max is 15 the number of element is 4 (from 3 to 10) if i changed the min to 10 and the max to 20 the number of element is 1 (20) because 20 is equal to the max

this is my code

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    vector<int> bebek;
    std::vector<int>::iterator low1, up1;
    int N,Q, input, input2, ct;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> input;
        bebek.push_back(input);
    }
    cin >> Q;
    for (int i = 0; i < Q; i++)
    {
        cin >> input >> input2;
        low1 = lower_bound(bebek.begin(), bebek.end(), input+1);
        up1 = upper_bound(bebek.begin(), bebek.end(), input2-1);
        cout << distance(low1, up1) << endl;

        

    }
    
    
    return 0;
}

input:
5 (number of the element in array)
3 6 8 10 20 (the elements)
2 (the number of min and max)
2 15 (min and max)
10 20 (min max 2nd)

expected output:
4
1

current output:
4
0

what can i do to improve my algorithm

HD-coders64
  • 19
  • 2
  • Is the input guaranteed to be sorted? – ph3rin Jun 24 '21 at 14:53
  • I think this can be solved with a binary index tree (Fenwick tree). – AndyG Jun 24 '21 at 14:57
  • @Meowmere yes it is the site say so – HD-coders64 Jun 24 '21 at 14:59
  • @AndyG can you elaborate in answer section – HD-coders64 Jun 24 '21 at 14:59
  • A BIT allows for efficient insertion, update, and query of frequency counts (all in logarithmic time). If your queries are interleaved with insert/update, then it's the most optimal data structure. Otherwise, if you already have all of your elements ahead of time, it's easiest to sort your collection and then use binary search to find offsets for min and max in order to perform a frequency count. – AndyG Jun 24 '21 at 15:03

1 Answers1

0

#include <bits/stdc++.h>
That is not a standard include file.

using namespace std;
Don't do that.

std::vector<int>::iterator low1, up1;
int N,Q, input, input2, ct;

Don't declare all your variables at the top like that!
Declare the variable where needed, and when it's ready to be initialized.
In particular, low1 and up1 are used inside an inner scope. They should just be declared there, and BTW use auto. E.g.

const auto low1 = lower_bound(bebek.begin(), bebek.end(), input+1);
const auto up1 = upper_bound(bebek.begin(), bebek.end(), input2-1);

Don't use the C macro NULL. C++ has the nullptr keyword.

It seems strange that you are peturbing your min and max values by +1 and -1 when searching. The definitions of ..._bound match what you are trying to do, so the supplied numbers should be just right.

"greater than min" upper_bound will point to the first element greater than the number. So, you're using the wrong function.

"lower or equal to the max" lower_bound will point to the first one equal. upper_bound will point to the first one greater, which means the ones before that is the count you want.

So, you are using the wrong bound function for the first call, and you should not be changing the min/max values from what was typed.

JDługosz
  • 5,592
  • 3
  • 24
  • 45
  • 1
    you are mixing suggestions about style with non-style. Moreover, there are situations where `using namespace std;` is ok and situations where it isnt. Just saying "Don't do that" does not help a bit to understand why to not use it. – 463035818_is_not_an_ai Jun 24 '21 at 15:07