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

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.