Hotel Queries

1#include<bits/stdc++.h>
2using namespace std;
3#define int long long
4struct node{
5  int l,r,v,m;
6  node *lf,*rg;
7  node(int _l,int _r,int a[]): l(_l),r(_r),m((_l+_r)>>1),v(0){
8    if(l==r) v=a[l];
9    else
10      lf=new node(l,m,a),
11      rg=new node(m+1,r,a),
12      v=max(lf->v,rg->v);
13  }
14  int qry(int x){
15    if(l==r){
16      return l;
17    }
18    return (lf->v<x?rg->qry(x):lf->qry(x));
19  }
20  void upd(int x,int cv){
21    if(l==r){
22      v=cv;
23      return;
24    }
25    (x<=m?lf:rg)->upd(x,cv);
26    v=max(lf->v,rg->v);
27  }
28}*root;
29signed main(){
30  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
31  int n,m; cin>>n>>m;
32  int a[n];
33  for(int i=0;i<n;++i) cin>>a[i];
34  root=new node(0,n-1,a);
35  while(m--){
36    int x; cin>>x;
37    if(x>root->v) cout<<"0 ";
38    else{
39      int u=root->qry(x);
40      a[u]-=x;
41      root->upd(u,a[u]);
42      cout<<u+1<<" ";
43    }
44  }
45  cout<<'\n';
46  return 0;
47}