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.

Powered By
CHP Adblock Detector Plugin | Codehelppro