fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. int n,m,h[500005],r[500005],st[2000006];
  5. void UPDATE(int id, int l, int r, int i, int v)
  6. {
  7.     if (l>i || r<i) return;
  8.     else if (l==r)
  9.     {
  10.         st[id]=v;
  11.         return;
  12.     }
  13.     int mid=(l+r)/2;
  14.     if (i<=mid) UPDATE(id*2,l,mid,i,v);
  15.     else UPDATE(id*2+1,mid+1,r,i,v);
  16.     st[id]=max(st[id*2],st[id*2+1]);
  17. }
  18. void UPDATE(int i, int v)
  19. {
  20.     UPDATE(1,1,n,i,v);
  21. }
  22. int GET(int id, int l, int r, int u, int v, int vl)
  23. {
  24.     if (st[id]<vl) return 0;
  25.     else if (l==r) return l;
  26.     int mid=(l+r)/2;
  27.     int res1=GET(id*2,l,mid,u,v,vl);
  28.     if (res1) return res1;
  29.     else
  30.     {
  31.         int res2=GET(id*2+1,mid+1,r,u,v,vl);
  32.         if (res2) return res2;
  33.     }
  34.     return 0;
  35. }
  36. int GET(int u, int v, int vl)
  37. {
  38.     return GET(1,1,n,u,v,vl);
  39. }
  40. signed main()
  41. {
  42.     ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  43.     cin>>n>>m;
  44.     for (int i=1;i<=n;i++) cin>>h[i],UPDATE(i,h[i]);
  45.     for (int i=1;i<=m;i++)
  46.     {
  47.         cin>>r[i];
  48.         int ans=GET(1,n,r[i]);
  49.         cout<<ans<<' ';
  50.         if (ans) UPDATE(ans,h[ans]-r[i]),h[ans]-=r[i];
  51.     }
  52.     return 0;
  53. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/C1pN1l
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!