fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int binarySearch(vector<pair<int, int>>arr, int tar)
  6. {
  7.     int st = 0, end = arr.size()-1;
  8.     while(st <= end)
  9.     {
  10.         int mid = st + (end - st)/2;
  11.         if((arr[mid].second - (arr[mid].first-1)) <= tar && tar <= arr[mid].second)
  12.             return mid+1;
  13.         else if(tar < (arr[mid].second - arr[mid].first))
  14.         {
  15.             end = mid - 1;
  16.         }
  17.         else
  18.         {
  19.             st = mid + 1;
  20.         }
  21.     }
  22.     return -1;
  23. }
  24.  
  25. int main()
  26. {
  27.     int n;
  28.     long long sum = 0;
  29.     cin >> n;
  30.     vector<pair<int, int>> arr(n);
  31.     for(int i = 0; i<n; i++)
  32.     {
  33.         cin >> arr[i].first;
  34.         sum += arr[i].first;
  35.         arr[i].second = sum;
  36.     }
  37.     int m;
  38.     cin >> m;
  39.     vector<int> brr(m);
  40.     for(int i = 0; i<m; i++)
  41.     {
  42.         cin >> brr[i];
  43.     }
  44.     for(int i = 0; i<m; i++)
  45.     {
  46.         int ans = binarySearch(arr, brr[i]);
  47.         cout << ans << endl;
  48.     }
  49.     return 0;
  50. }
  51.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
5
2 7 3 4 9
3
1 25 11
stdout
copy 
1
5
3
https://ideone.com/tZoQr9
474B codeforces - worms
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!