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


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;
}