Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /***************************************************************************
- * ####### # *
- * # # # ###### # # # # #### # # # # # *
- * # # # # # # ## # # # # # # # *
- * # ###### ##### # # # # # #### ###### # # # *
- * # # # # ####### # # # # # # # # # *
- * # # # # # # # ## # # # # # # # *
- * # # # ###### # # # # #### # # #### ###### *
- ***************************************************************************/
- #include<bits/stdc++.h>
- #define ll long long
- #define pb push_back
- #define endl '\n'
- #define pii pair<ll int,ll int>
- #define vi vector<ll int>
- #define all(a) (a).begin(),(a).end()
- #define F first
- #define S second
- #define sz(x) (ll int)x.size()
- #define hell 1000000007
- #define rep(i,a,b) for(ll int i=a;i<b;i++)
- #define lbnd lower_bound
- #define ubnd upper_bound
- #define bs binary_search
- #define mp make_pair
- using namespace std;
- #define N 100005
- ll binarySearch(vi arr, ll l, ll r, ll x)
- {
- if(x<arr[0])
- return -1;
- else if(x>=arr[r])
- return r;
- while (l <= r)
- {
- ll m = l + (r-l)/2;
- // Check if x is present at mid
- if (arr[m] == x)
- return m;
- // If x greater, ignore left half
- if (arr[m] < x)
- l = m + 1;
- // If x is smaller, ignore right half
- else
- r = m - 1;
- }
- // if we reach here, then element was
- // not present
- return l-1;
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- int TESTS=1;
- // cin>>TESTS;
- while(TESTS--)
- {
- ll n,q,x;
- cin>>n>>q;
- vi a(n),dp(n);
- rep(i,0,n)
- cin>>a[i];
- sort(all(a));
- dp[0]=a[0];
- rep(i,1,n)
- dp[i]=dp[i-1]+a[i];
- rep(i,0,q)
- {
- cin>>x;
- cout<<binarySearch(dp,0,n-1,x)+1<<endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement