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; } }