HackerEarth Xsquare And Number List problem solution

In this HackerEarth Xsquare And Number List problem solution 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.

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.

HackerEarth Xsquare And Number List problem solution.

#include <bits/stdc++.h>
using namespace std ;
#define LL long long int
#define ft first
#define sd second
#define PII pair<int,int>
#define MAXN 1000001
#define mp make_pair
#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)
#define sc(x) scanf("%d",&x)
#define scll(x) scanf("%lld",&x)
#define pr(x) printf("%d\n",x)
#define pb push_back
#define MOD 1000000007
#define inf INT_MAX/2
#define ASST(X,L,R) assert(X >= L && X <= R)
int N,Q ;
vector<int> A ;

int power(int a,int b){
    int res = 1 ;
    while(b){
        if(b%2){
            res = (1LL * res * a) % MOD ;
        }
        b /= 2 ;
        a = (1LL * a * a) % MOD ;
    }
    return res ;
}

int less_than_X(int X){
    X -- ;
    int c = upper_bound(A.begin(),A.end(),X)-A.begin() ;
    return power(2,c) ;
}
int less_than_equals_to_X(int X){
    int c = upper_bound(A.begin(),A.end(),X)-A.begin() ;
    return power(2,c) ;
}

int main(){

    sc(N) ;
    sc(Q) ;
    ASST(N,1,500000) ;
    ASST(Q,1,500000) ;
    A.resize(N) ;
    for(int i=0;i<N;i++){
        sc(A[i]) ;
        ASST(A[i],1,1000000000) ;
    }
    sort(A.begin(),A.end()) ;
    char ch ;
    int X;
    int total_subsets = power(2,N) ;
    while(Q--){
        cin >> ch ;
        sc(X) ;
        assert(ch == '>' || ch == '<' || ch == '=') ;
        ASST(X,1,1000000000) ;
        int ans = 0 ;
        switch(ch){
            case '<' : pr(less_than_X(X)) ;
                        break ;
            case '>' : ans = less_than_equals_to_X(X) ;
                       ans = total_subsets - ans ;
                       if( ans < 0 )
                            ans += MOD ;
                       pr(ans) ;
                        break ;
            case '=' : ans = less_than_equals_to_X(X) ;
                       ans -= less_than_X(X) ;
                       if( ans < 0 )
                            ans += MOD ;
                       pr(ans) ;
                        break ;
        }
    }
    return 0 ;
}

Second solution

#include <bits/stdc++.h>
#define MAX 500005
#define lli long long
#define M 1000000007

using namespace std;

int A[500005];
lli pow2[500005];

void pre()
{
    pow2[0] = 1;
    for ( int i = 1; i <= 500001; i++ ) {
        pow2[i] = pow2[i-1] + pow2[i-1];
        if ( pow2[i] >= M ) pow2[i] -= M;
    }
    return;
}

int main()
{
    pre();
    int n,q,x;
    char s[2];
    scanf("%d%d", &n, &q);
    assert(n<=500000);
    assert(q<=500000);
    for ( int i = 0; i < n; i++ ) {
        scanf("%d", &A[i]);
        assert(A[i] >= 1 && A[i]<=1000000000);
    }
    sort(A,A+n);
    while ( q-- ) {
        scanf("%s%d", &s, &x);
        assert(x>=1&&x<=1000000000);
        if ( s[0] == '=' ) {
            int idx2 = upper_bound(A,A+n,x) - A;
            idx2--;
            int idx1 = lower_bound(A,A+n,x) - A;
            if ( idx1 == n || A[idx1] > x ) {
                printf("0\n");
                continue;
            }
            lli ans1 = pow2[idx1];
            lli ans2 = pow2[idx2-idx1+1] - 1;
            if ( ans2 < 0 ) ans2 += M;
            printf("%lld\n", (ans1*ans2)%M);
        }
        else if ( s[0] == '<' ) {
            int idx = lower_bound(A, A+n, x) - A;
            idx--;
            lli ans1;
            else ans1 = pow2[idx+1];
            printf("%lld\n", ans1);
        }
        else {
            int idx = upper_bound(A,A+n,x) - A;
            lli ans1 = pow2[idx];
            lli ans2 = pow2[n-idx] - 1;
            if ( ans2 < 0 ) ans2 += M;
            printf("%lld\n", (ans1*ans2)%M);
        }
    }
    return 0;
}