Square Game

QUESTION

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.\nFor example :\nConsider the following multi set consisting of 3 elements S = {1,2,3}. \nList of all subsets:\n{}\n{1}\n{2}\n{3}\n{1,2}\n{2,3}\n{1,3}\n{1,2,3}\nFinal List:\n{0}\n{1}\n{2}\n{3}\n{2}\n{3}\n{3}\n{3}\nNow, Xsquare wonders that given an integer K how many elements in the final list are greater than ( > ) , less than ( < ) or equals to ( == ) K.\nTo 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.\n > K : Count the number of elements X in the final list such that X > K.\n < K : Count the number of elements X in the final list such that X < K.\n = K : Count the number of elements X in the final list such that X == K.\nNote:\n Answer to a particular query can be very large. Therefore, Print the required answer modulo 109+7.\n An empty subset is replaced by an integer 0.\nInput\nFirst 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.\nOutput\nFor each query, print the required answer modulo 109+7.\n.

“TESTCASE_1”: “3 5\n1 2 3\n< 1\n> 1\n= 3\n= 2\n> 3\n###—###SEPERATOR—###—\n1\n6\n4\n2\n0”, “TESTCASE_2”: “3 5\n2 3 4\n< 2\n> 3\n= 1\n= 2\n> 2\n###—###SEPERATOR—###—\n1\n4\n0\n1\n6”, “TESTCASE_3”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

#include<bits/stdc++.h>
#define ll long long int
#define mod 1000000007
using namespace std;
 
ll power(ll a,ll b)
{
     ll res=1;
     while(b)
     {
         if(b&1)
             res=(res*a)%mod;
         a=(a*a)%mod;
         b/=2;
     }
     return res;
}
int main()
{
     ll n,q,i,ans,ans1;
     scanf("%lld%lld",&n,&q);
     ll arr[n];
     for(i=0;i<n;i++)
        scanf("%lld",&arr[i]);
     ll x,l,r;
     char ch;
     sort(arr,arr+n);
     while(q--)
     {
         cin>>ch;
         scanf("%lld",&x);
        // cout<<ch;
         if(ch=='=')
         {
             r=upper_bound(arr,arr+n,x)-arr;
             ans1=(power(2,n)-power(2,r)+mod+mod)%mod;
             x--;
             l=upper_bound(arr,arr+n,x)-arr;
             ans=power(2,l);
             ans=(power(2,n)-ans-ans1+mod+mod)%mod;
            // cout<<l<<" "<<r<<" "<<(r-l+1)<<endl;
             //ans=power(2,r-l+1);
         }
         else if(ch=='<')
         {
             x--;
             r=upper_bound(arr,arr+n,x)-arr;
             ans=(power(2,r)+mod)%mod;
            // cout<<r<<endl;
         }
         else
         {
             r=upper_bound(arr,arr+n,x)-arr;
             ans=(power(2,n)-power(2,r)+mod+mod)%mod;
             //cout<<r<<endl;
         }
         ans=(ans+mod)%mod;
         printf("%lld\n",ans);
     }
}
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