Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef vector<int> VI;
- typedef vector<VI> VVI;
- #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
- #define REP(i, n) FOR(i, 0, n)
- #define INF (1LL<<25) //33554432
- int d[100010];
- signed main(void)
- {
- //入力
- int n, m;
- scanf("%d%d", &n, &m);
- VVI a(n, (VI(m, 0)));
- REP(i, n) REP(j, m) scanf("%d", &a[i][j]);
- //降順でない列が開始する行
- int s = -1;
- //降順でない部分列が何行から何行に存在するのかを求める
- REP(i, m) {
- s = -1;
- FOR(j, 1, n) {
- if(a[j][i] >= a[j-1][i]) {
- if(s == -1) s = j-1;
- d[s] = max(d[s], (int)j);
- } else {
- s = -1;
- }
- }
- }
- //例として0行から3行が降順でない列のときd[0] = 3となっている
- //d[1] = d[2] = d[3] = 3 と間を埋める
- int ret = -INF;
- REP(i, n) {
- ret = max(ret, d[i]);
- if(ret < i) ret = i;
- d[i] = ret;
- }
- //クエリに答える
- int k;
- scanf("%d", &k);
- REP(i, k) {
- int l, r;
- scanf("%d%d", &l, &r);
- l--; r--;
- if(l == r) {
- //数1個からなる数列は降順でない列
- cout << "Yes" << endl;
- } else if(d[l] >= r) {
- //rが最大の降順でない行以下ならば降順でない列が存在する
- cout << "Yes" << endl;
- } else {
- cout << "No" << endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement