lower_bound ABC 322 C - Festivalを理解し忘れないようにする。

https://atcoder.jp/contests/abc322/tasks/abc322_c

問題概要

$N$日間、まつりが開催される。その中で$A{\tiny 1}...A{\tiny M}$日に花火が打ち上がる。
また最終日となる$N$日目、つまり$A{\tiny M}$日目は必ず花火が打ち上がる。

i日目以降で、花火が打ち上がるのはi日目から数えて何日目か?

実装方針

O(NM)の削減方法を考える。
i日目から計算して最短で花火が上がる日を求めたい。$最短で花火が上がる日 - i日目$が答えになる。
2部探索のlower_boundを使用することで「最短で花火が上がる日」を求められる。

提出コード

コード

#include <iostream>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <regex>
#include <iomanip>
#include <map>
#include <cassert>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
using namespace std;
using ll = long long;
template<class T> using P = pair<T, T>;
template<typename T> bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template<typename T> bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }
using G = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i,j, n) for (int i = j; i < n; i++)
#define all(x) (x).begin(), (x).end()
const double PI = acos(-1);
const int MI = 1e8;
const ll MLL = 1e18;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(m);
    rep(i,m) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        int t = *lower_bound(all(a),i);
        cout << t - i << endl;
    }
    return 0;
}