開通777年記念 [yukicoder No.607] - はまやんはまやんはまやん

前提知識

累積和

解法

https://yukicoder.me/submissions/222019

本解法では累積和とlower_boundの解法であるが、O(NMlogM)解法である。
公式解説では尺取り法を用いておりO(NM)なので、尺取り法のやり方も知っておくべきである。
（累積和とlower_bound(O(logN))が尺取り法(ならしO(1))で解決できることはよくある）

まず、車両の乗車人数は前の区間と比べた増減の値になっているので、それを計算して、実際の乗車人数に直そう。
次に、各車両について区間の和が777となる区間を探すが、自分は累積和とlower_boundでそれを実現した。
　
各車両について区間の乗車人数の累積和をとっておく。
つまり「A[i][j] := i番目の車両の[0,j]の区間の乗車人数」を計算する。
すると、i番目の車両の区間[s..t]の乗車人数を計算したい時はA[i][t] - A[i][s - 1]とすればいい。
後は、考える区間の右端tを全探索するが「A[i][t] - A[i][s - 1]=777」が満たされればいいので「A[i][s - 1]=A[i][t]-777」となるsを探せばいいことになる。
これは累積和は単調増加しているので、lower_boundを使えば高速にsを探し出せる。

int N, M;
int A[1010][1010];
#define no "NO"
#define yes "YES"
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) rep(j, 0, N) cin >> A[i][j];
    rep(i, 1, M) rep(j, 0, N) A[i][j] += A[i - 1][j];
    rep(i, 0, M) rep(j, 1, N) A[i][j] += A[i][j - 1];

    string ans = no;
    rep(i, 0, M) {
        rep(j, 0, N) {
            int d = A[i][j] - 777;
            if (d < 0) continue;
            if (d == 0) ans = yes;
            int k = lower_bound(A[i], A[i] + j, d) - A[i];
            if (k != j) if (A[i][j] - A[i][k] == 777) ans = yes;
        }
    }
    cout << ans << endl;
}