Advertisement
Guest User

Untitled

a guest
May 1st, 2018
5,445
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.09 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define sc(a) scanf("%d",&a)
  6. #define scll(a) scanf("%lld",&a)
  7.  
  8. typedef long long ll;
  9.  
  10. const int MAX = 2e5 + 11;
  11.  
  12. ll a[MAX],csum[MAX];
  13. int n;
  14.  
  15. int bs(int pos,ll &hits,ll val)
  16. {
  17.     if(val + hits < a[pos])
  18.     {
  19.         hits += val;
  20.         return pos;
  21.     }
  22.     int st = pos,en = n;
  23.     int ret;
  24.     while(st <= en)
  25.     {
  26.         int md = (st + en)>>1;
  27.         if(csum[md] - csum[pos - 1] - hits <= val)
  28.             st = md + 1,ret = md;
  29.         else
  30.             en = md - 1;
  31.     }
  32.     if(ret == n)
  33.     {
  34.         hits = 0;
  35.         return 1;
  36.     }
  37.     ret++;
  38.     ll tmp = csum[ret] - csum[pos - 1] - hits - val;
  39.     hits = a[ret] - tmp;
  40.     return ret;
  41. }
  42.  
  43. int main()
  44. {
  45.     int q;
  46.     sc(n);
  47.     sc(q);
  48.  
  49.     ll sm = 0;
  50.  
  51.     for(int i=1;i<=n;++i)
  52.     {
  53.         scll(a[i]);
  54.         csum[i] = csum[i - 1] + a[i];
  55.     }
  56.  
  57.     int cur = 1;
  58.     ll hits = 0;
  59.  
  60.     for(int i=0;i<q;++i)
  61.     {
  62.         ll x;
  63.         scll(x);
  64.         cur = bs(cur,hits,x);
  65.         printf("%d\n",n - cur + 1);
  66.     }
  67.  
  68.     return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement