fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<cmath>
  5. typedef long long ll;
  6.  
  7. using namespace std;
  8.  
  9. int main(){
  10.     ll num, q;
  11.     cin >> num >> q;
  12.     ll n = log2(2 * num - 1);
  13.     n = pow(2, n);
  14.     vector<ll> tree(2 * n, 0);
  15.  
  16.     for(int i = 0; i < num; i++){
  17.         cin >> tree[i + n];   
  18.     }
  19.  
  20.     for(int i = n - 1; i >= 0; i--){
  21.         ll k = i;
  22.         while(k > 0){
  23.             tree[k] = max(tree[2 * k], tree[2 * k + 1]);
  24.             k /= 2;
  25.         }
  26.     }
  27.  
  28.     while(q--){
  29.         int group, i = 1;
  30.         cin >> group;
  31.         if(tree[1] < group)cout << 0 << " ";
  32.         else{
  33.             while(i < tree.size()/2){
  34.                 if(tree[2 * i] >= group)i = 2*i;
  35.                 else if(tree[2 * i + 1] >= group)i = 2 * i + 1;
  36.                 else break;
  37.             }
  38.             cout<<i - n + 1<<" ";
  39.             tree[i] -= group;
  40.             while(i > 0){
  41.                 i /= 2;
  42.                 tree[i] = max(tree[2 * i], tree[2 * i + 1]);
  43.             }
  44.         }
  45.     }
  46. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
10 10
7 2 9 5 1 2 1 1 2 5
7 5 6 4 8 3 9 10 1 6
stdout
copy 
1 3 0 3 0 4 0 0 2 0
https://ideone.com/CN9R3n
language:
C++ (gcc 8.3)
created:
6 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!