Codeforces #401 C. Alyona and Spreadsheet

• 概要
  n ✕ mの整数テーブルが与えられる。加えて整数kとk個のl[i],r[i]が与えられる。 テーブルのうち、l[i]からr[i]が単調増加(a[i][j] <= a[i][j+1])ならYes, そうでなければNoを出力する。

• 方針 a[i][j] <= a[i+1][j] かつi<n-1のとき dp[i] = dp[i+1] + 1 それ以外のとき dp[i] = 1 とする。 列ごとにdp[i]を作成し、ans[i] = max(ans[i], dp[i])とする。 l[i] - r[i] +1 <= ans[l[i]-1] のときYes, そうでないときNoを出力

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

int main() {
    int n, m;
    cin >> n >> m;
    ll a[n][m];
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            cin >> a[i][j];
        }
    }
    vector<int> ans(n, 0);
    for(int i=0;i<m;i++) {
        vector<ll> v(n);
        for(int j=n-1;j>=0;j--) {
            if(j == n-1)
                v[j] = 1;
            else if(a[j][i] > a[j+1][i])
                v[j] = 1;
            else
                v[j] = v[j+1] + 1;
            ans[j] = max<ll>(ans[j], v[j]);
        }
    }

    int k;
    cin >> k;
    for(int i=0;i<k;i++) {
        int l, r;
        cin >> l >> r;
        if(ans[l-1] >= r - l + 1)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}