Question Name: Xsquare And Number List

#include<bits/stdc++.h>
 
using namespace std;
 
#define i64 long long
#define MOD 1000000007
 
i64 bigMod(i64 n){
 
    if(n == 0)
        return 1;
    if(n&1)
        return (2*bigMod(n-1))%MOD;
    i64 x = bigMod(n/2);
    return (x*x)%MOD;
}
 
int main(){
 
    i64 n, q, tmp, k;
    char ch;
    vector<i64> v;
    scanf("%lld%lld", &n, &q);
    for(int i = 0; i < n; i++){
 
        scanf("%lld", &tmp);
        v.push_back(tmp);
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < q; i++){
        getchar();
        scanf("%c%lld", &ch, &k);
        if(ch == '<'){
            i64 x = lower_bound(v.begin(), v.end(), k)-v.begin();
            printf("%lld\n", bigMod(x));
 
        }
        else if(ch == '>'){
 
            i64 x = upper_bound(v.begin(), v.end(), k)-v.begin();
            printf("%lld\n", (bigMod(n)-bigMod(x)+MOD)%MOD);
        }
        else{
 
            i64 x = upper_bound(v.begin(), v.end(), k)-v.begin();
            i64 y = lower_bound(v.begin(), v.end(), k)-v.begin();
            printf("%lld\n", (bigMod(x)-bigMod(y)+MOD)%MOD);
        }
    }
    return 0;
}

• Problem Description
  Xsquare loves to play with numbers a lot. Today, he has a multi set S consisting of N integer elements. At first, he has listed all the subsets of his multi set S and later replaced all the subsets with the maximum element present in the respective subset.
  
  For example :
  
  Consider the following multi set consisting of 3 elements S = {1,2,3}.
  List of all subsets:
  1. { } or , the empty set, sometimes called the “null” set.
  2. {1}
  3. {2}
  4. {3}
  5. {1,2}
  6. {1,3}
  7. {2,3}
  8. {1,2,3}
  
  Final List:
  {0}
  {1}
  {2}
  {3}
  {2}
  {3}
  {3}
  {3}
  
  
  
  Now, Xsquare wonders that given an integer K how many elements in the final list are greater than ( > ) , less than ( < ) or equals to ( == ) K.
  
  To make this problem a bit more interesting, Xsquare decided to add Q queries to this problem. Each of the queries has one of the following type.
  
  > K : Count the number of elements X in the final list such that X > K.
  < K : Count the number of elements X in the final list such that X < K.
  = K : Count the number of elements X in the final list such that X == K.
  Note:
  
  Answer to a particular query can be very large. Therefore, Print the required answer modulo 109+7.
  An empty subset is replaced by an integer 0.
  Input
  
  First line of input contains two space separated integers N and Q denoting the size of multiset S and number of queries respectively. Next line of input contains N space separated integers denoting elements of multi set S. Next Q lines of input contains Q queries each having one of the mentioned types.
  
  Output
  
  For each query, print the required answer modulo 109+7.
  
  Constraints:
  
  1 N,Q 5*10^5
  1 K,Si 10^9
  query_type = { < , > , = }
  Warning :
  
  Prefer to use printf / scanf instead of cin / cout.
• Test Case 1
  Input (stdin)3 5
  1 2 3
  < 1
  > 1
  = 3
  = 2
  > 3
  Expected Output1
  6
  4
  2
  0
• Test Case 2
  Input (stdin)2 5
  2 4
  < 1
  > 1
  = 3
  = 2
  > 3
  Expected Output1
  3
  0
  1
  2

Search for: