http://codeforces.com/contest/777/problem/C

$n$行$m$列の行列が与えられる.列方向の$[l, r]$が広義の単調増加になっている列がある場合は$Yes$を,そうではない場合は$No$を返す.

一列ずつどこからどこまでが単調増加になっているかの区間を求める.区間の小さい方が同じ場合は$max$を取ってより大きい区間にする.小さい方から順番に見ていく時に,それよりも前に見た区間の右端の方が大きい場合は,覆われている場合なので,今までみた$max$の値を持っておき,その値より小さければ更新する.区間の中に質問の$[l, r]$が含まれているかの問題になるので,$l$を含む区間の最大の右端が$r$より大きければ,その区間が単調増加になっていることが分かる.

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,k,n) for(int i=k;i<(int)(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int ma[100005], cnt[100005];

int main() {
	cin.tie(0);
    ios::sync_with_stdio(false);

	int n, m;
	cin >> n >> m;

	vector<ll> pre(m), now(m);
	rep(i, m) cin >> pre[i];

	memset(ma, 0, sizeof(ma));
	memset(cnt, 0, sizeof(cnt));

	rep(i, n) {
		ma[i+1] = i+1;
	}

	rep(i, n-1) {
		rep(j, m) cin >> now[j];

		rep(j, m) {
			if(pre[j] <= now[j]) {
				cnt[j]++;
				int d = ma[i+2-cnt[j]];
				ma[i+2-cnt[j]] = max(d, i + 2);
			} else {
				cnt[j] = 0;
			}
		}
		pre = now;
	}

	int t = 0;
	rep(i, n + 1) {
		t = max(ma[i], t);
		ma[i] = max(ma[i], t);
	}

	int k;
	cin >> k;
	rep(i, k) {
		int l, r;
		cin >> l >> r;

		if(r <= ma[l]) cout << "Yes" << endl;
		else cout << "No" << endl;
	}

	return 0;
}