Advertisement
TheAnshul

Lancel And Wine

Jun 17th, 2018
194
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***************************************************************************
  2.  * #######                    #                                            *
  3.  *    #     #    #  ######   # #    #    #   ####   #    #  #    #  #      *
  4.  *    #     #    #  #       #   #   ##   #  #       #    #  #    #  #      *
  5.  *    #     ######  #####  #     #  # #  #   ####   ######  #    #  #      *
  6.  *    #     #    #  #      #######  #  # #       #  #    #  #    #  #      *
  7.  *    #     #    #  #      #     #  #   ##  #    #  #    #  #    #  #      *
  8.  *    #     #    #  ###### #     #  #    #   ####   #    #   ####   ###### *
  9.  ***************************************************************************/
  10. #include<bits/stdc++.h>
  11. #define ll          long long
  12. #define pb          push_back
  13. #define endl        '\n'
  14. #define pii         pair<ll int,ll int>
  15. #define vi          vector<ll int>
  16. #define all(a)      (a).begin(),(a).end()
  17. #define F           first
  18. #define S           second
  19. #define sz(x)       (ll int)x.size()
  20. #define hell        1000000007
  21. #define rep(i,a,b)  for(ll int i=a;i<b;i++)
  22. #define lbnd        lower_bound
  23. #define ubnd        upper_bound
  24. #define bs          binary_search
  25. #define mp          make_pair
  26. using namespace std;
  27.  
  28. #define N  100005
  29. ll binarySearch(vi arr, ll l, ll r, ll x)
  30. {
  31.     if(x<arr[0])
  32.         return -1;
  33.     else if(x>=arr[r])
  34.         return r;
  35.     while (l <= r)
  36.     {
  37.         ll m = l + (r-l)/2;
  38.  
  39.         // Check if x is present at mid
  40.         if (arr[m] == x)
  41.             return m;
  42.  
  43.         // If x greater, ignore left half
  44.         if (arr[m] < x)
  45.             l = m + 1;
  46.  
  47.         // If x is smaller, ignore right half
  48.         else
  49.             r = m - 1;
  50.     }
  51.  
  52.     // if we reach here, then element was
  53.     // not present
  54.     return l-1;
  55. }
  56. int main()
  57. {
  58.     ios_base::sync_with_stdio(false);
  59.     cin.tie(0);
  60.     cout.tie(0);
  61.     int TESTS=1;
  62. //  cin>>TESTS;
  63.     while(TESTS--)
  64.     {
  65.         ll n,q,x;
  66.         cin>>n>>q;
  67.         vi a(n),dp(n);
  68.         rep(i,0,n)
  69.         cin>>a[i];
  70.         sort(all(a));
  71.         dp[0]=a[0];
  72.         rep(i,1,n)
  73.         dp[i]=dp[i-1]+a[i];
  74.         rep(i,0,q)
  75.         {
  76.             cin>>x;
  77.             cout<<binarySearch(dp,0,n-1,x)+1<<endl;
  78.         }
  79.     }
  80.     return 0;
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement