D - Kth Excluded

・問題URL

https://atcoder.jp/contests/abc205/tasks/abc205_d

・発想

・Q個のクエリに答えるので各クエリにかけれる時間はlonNくらい
・「使える数」の配列を作ろうとするとメモリオーバー
・上二つ組み合わせると二分探索カナ～

・解法

やはり二分探索。Kの前に何個使えない数があるか知りたいので、逆にKの前の使える数の累積和を出しておく。lower_boundでindexを求めたらあとは簡単。めっちゃでかい数（10¹⁸よりややでかい）をuse[N]として宣言したのは解説より賢い（黙れ）。
（ちなみにINF=10¹⁸にしたつもりが10¹²で謎のWA食らった。草）

・コード

int main(){
  
  ll N,Q;
  cin>>N>>Q;
  vector<ll>A(N),use(N+1);
  rep(i,N)cin>>A[i];
  
  use[0]=A[0]-1;
  for(int i=1;i<N;i++)use[i]=use[i-1]+(A[i]-A[i-1]-1);
  use[N]=3*INF;
 
  rep(i,Q){
    ll K;
    cin>>K;
    auto itr=lower_bound(use.begin(),use.end(),K);
    ll idx=itr-use.begin();
    cout<<K+idx<<endl;
  }
}