Untitled
user_5668965
c_cpp
13 days ago
1.1 kB
1
Indexable
Never
#include<bits/stdc++.h> using namespace std; #define sc(a) scanf("%d",&a) #define scll(a) scanf("%lld",&a) typedef long long ll; const int MAX = 2e5 + 11; ll a[MAX],csum[MAX]; int n; int bs(int pos,ll &hits,ll val) { if(val + hits < a[pos]) { hits += val; return pos; } int st = pos,en = n; int ret; while(st <= en) { int md = (st + en)>>1; if(csum[md] - csum[pos - 1] - hits <= val) st = md + 1,ret = md; else en = md - 1; } if(ret == n) { hits = 0; return 1; } ret++; ll tmp = csum[ret] - csum[pos - 1] - hits - val; hits = a[ret] - tmp; return ret; } int main() { int q; sc(n); sc(q); ll sm = 0; for(int i=1;i<=n;++i) { scll(a[i]); csum[i] = csum[i - 1] + a[i]; } int cur = 1; ll hits = 0; for(int i=0;i<q;++i) { ll x; scll(x); cur = bs(cur,hits,x); printf("%d\n",n - cur + 1); } return 0; }
Leave a Comment