C. Valhalla Siege

• Quiz
  • https://codeforces.com/problemset/problem/975/C
• AC
  • https://codeforces.com/contest/975/submission/98419257
• 問題理解
  • Lagerthaが矢を放つ
  • Ivar軍には兵士がいて、矢は前の人から刺さる
  • 兵士が全滅した時のみ、全員復活する
• 解法
  • 各クエリにて、今までに放たれた矢の累積で、どこまでの兵士が死んでいるかを二分探索
  • 兵士の数は累積和にすることで単調増加となり、二分探索可能になる

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,Q;
    cin>>N>>Q;

    VI A(N);
    rep(i, N) cin >> A[i];

    rep(i,N-1){
      A[i+1] += A[i];
    }    

    ll attack=0;
    while(Q--){
      ll k;cin>>k;
      attack+=k;
      auto it = upper_bound(ALL(A), attack);
      if(it==A.end()){
        // revive
        attack=0;
        p(N);
      }
      else{
        ll i = it-A.begin();
        ll live = N-i;
        p(live);
      }
    }

    return 0;
}