title: How to run this code in less than 1 second?
body: <p>How can I solve this problem without getting time limit exceeded </p>
  
  <p><a href="http://codeforces.com/problemset/problem/474/B" rel="nofollow">http://codeforces.com/problemset/problem/474/B</a></p>
  
  <p>I tried putting all ranges in a 2D vector then looking for the desired index using binary search but it seems that the loop in the fn <code>BS()</code> takes a lot to execute as the size of the vector can be 10^6. </p>
  
  <p>here is my code:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;vector&gt;
  using namespace std;
  
  int Search(vector &lt;vector&lt;int&gt; &gt; a,int key){
      int start = 0;
      int end = a.size() - 1;
      while (start &lt;= end){
          int mid = start + (end - start) / 2;
          if (a[mid][0] &gt; key &amp;&amp; a[mid][1] &gt; key){
              end = mid - 1;
          }
          else if (a[mid][0] &lt; key &amp;&amp; a[mid][1] &lt; key){
              start = mid + 1;
          }
          else {
              return mid;
          }
      }
  
      return -1;
  }
  vector &lt;int&gt; BS(vector &lt;vector &lt;int&gt; &gt; v, vector&lt;int&gt; keys){
      int j = 0;
      vector &lt;int&gt; piles;
      for (int i = 0; i &lt; keys.size(); i++){
          piles.push_back(Search(v, keys[i])+1);
      }
      return piles;
  }
  vector &lt; vector&lt;int&gt; &gt; Range(vector&lt;int&gt; v){
      vector &lt; vector&lt;int&gt; &gt; ranges(v.size());
      int sum1 = 1;
      int sum2 = v[0];
      for (int i = 0; i &lt; v.size(); i++){
          if (i == 0){
              ranges[i].push_back(sum1);
              ranges[i].push_back(v[i]);
              sum1 += v[i];
          }
          else{
              ranges[i].push_back(sum1);
              sum2 += v[i];
              ranges[i].push_back(sum2);
              sum1 += v[i];
          }
      }
      return ranges;
  }
  
  int main(){
      int n, m;
      cin &gt;&gt; n;
      vector &lt;int&gt; a, q;
  
      vector &lt; vector &lt;int&gt; &gt; v;
      for (int i = 0; i &lt; n; i++){
          int k;
          cin &gt;&gt; k;
          a.push_back(k);
      }
      cin &gt;&gt; m;
      for (int i = 0; i &lt; m; i++){
          int l;
          cin &gt;&gt; l;
          q.push_back(l);
      }
  
      v = Range(a);
  
      vector &lt;int&gt; jucy = BS(v, q);
  
  
      for (int i = 0; i &lt; jucy.size(); i++){
          cout &lt;&lt; jucy[i] &lt;&lt; endl;
      }
  
  
  
  
  }
  </code></pre>