Problem Statement      You used to have only 30 rocks, but now you have plenty of them. In fact, we will assume that you have a potentially infinite supply of rocks. You would like to show that you own over 9000 rocks. You have a set of boxes. You will choose a subset of those boxes and fill them with rocks so that the total number of rocks will be over 9000. Each box has a lower and an upper bound on the number of rocks it may contain. You are given the int[]s lowerBound and upperBound. For each i, the values lowerBound[i] and upperBound[i] have the following meaning: If you decide to use box i, the number of rocks you may put inside the box must be between lowerBound[i] and upperBound[i], inclusive. X is a positive integer that has two properties: X is over 9000. It is possible to select some of the boxes and fill them with appropriate numbers of rocks in such a way that the total number of rocks used is exactly X. Compute and return the number of possible values of X.   Definition      Class: Over9000Rocks Method: countPossibilities Parameters: int[], int[] Returns: int Method signature: int countPossibilities(int[] lowerBound, int[] upperBound) (be sure your method is public)        Constraints - lowerBound will contain between 1 and 15, elements, inclusive. - upperBound will contain the same number of elements as lowerBound. - Each element of lowerBound will be between 1 and 1,000,000 (10^6), inclusive. - Each element i of upperBound will be between lowerBound[i] and 1,000,000 (10^6), inclusive.   Examples 0)      {9000} {9001} Returns: 1 You can place 9000 or 9001 rocks in the single box. Of the allowed values, only 9001 is over 9000. 1)      {9000, 1, 10} {9000, 2, 20} Returns: 15 You have to choose box 0 and at least one other box, otherwise you have no chance of placing over 9000 rocks. If you only choose boxes 0 and 1, you can place 9001 or 9002 rocks. If you only choose boxes 0 and 2, you can place between 9010 and 9020 rocks, inclusive. If you choose all three boxes, you can place between 9011 and 9022 rocks, inclusive. Hence all possible values of X are 9001, 9002, and everything from 9010 to 9022, inclusive. 2)      {1001, 2001, 3001, 3001} {1003, 2003, 3003, 3003} Returns: 9 3)      {9000,90000,1,10} {9000,90000,3,15} Returns: 38 4)      {1,1,1,1,1,1} {3,4,5,6,7,8} Returns: 0 This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved. This problem was used for:        Single Round Match 539 Round 1 - Division I, Level One        Single Round Match 539 Round 1 - Division II, Level Two

Here we have to apply a bitmask of 2^n state so as to generate all possible bitmasked state. Now it is understood the for any subset {1,2,3}. we can generate all numbers between  low[1]+low[2]+low[3] to high[1]+high[2]+high[3] Now we can form a simple array and update freq[low]++ and freq[high+1]-- . And after forming the prefix all indices that have value greater than 1 can be generated. But this solution gives a memory timed out exception . So we need to realise the points in form of segments and apply a line sweep through them.The code is there for understanding

#include<bits/stdc++.h>

using namespace std;

int cost[20];

int unit[20];

int dp[210];

int idx=0;

#define inf 10000000

#define ff first

#define ss second

#define mp make_pair

#define pb push_back

int countPossibilities(vector<int> low, vector<int> high )

{

  int n=low.size();

  int val=(1<<n)-1;

  int mx=0;

   vector<pair<int,int> > inv;

  for(int i=1;i<=val;i++)

  {

      int sumi=0;

      int sumx=0;

     

      for(int j=0;j<n;j++)

      {

             if(i>>j &1 )

  {

    sumi+=low[j];

sumx+=high[j];

  }

}

//   cout<<"sumi "<<sumi<<" "<<sumx<<endl;

  mx=max(sumx,mx);

   

       inv.pb(mp(sumi,sumx));

}

int ans=0;

    sort(inv.begin(),inv.end());

    n=inv.size();

//     for(int i=0;i<n;i++)

 //   {

   //   cout<<inv[i].ff<<" "<<inv[i].ss<<endl;

//}

    int s=inv[0].ff;

    int end=inv[0].ss;

    for(int i=1;i<n;i++)

    {

      if(end>=inv[i].ff)

      {

        end=max(end,inv[i].ss);

  }

  else

  {

      if(end<=9000)

      {

        ans+=0;

}

else

{

ans+=(end-max(9001,s))+1;

}

      s=inv[i].ff;

      end=inv[i].ss;

  }

}

if(end>9000)

{

 ans+=(end-max(s,9001))+1;

}

  return ans;

}

int main()

{

 int n,m;

 cin>>n;

 int xx;

 vector<int> a,b;

 for(int i=0;i<n;i++)

 {

        cin>>xx;

        a.push_back(xx);

 }

 for(int i=0;i<n;i++)

 {

    cin>>xx;

    b.push_back(xx);

 }

 

 

 cout<< countPossibilities(a,b)<<endl;

 return 0;

}