Solution for codeforces round 401, C

codeforces_401_C.cpp

#include <bits/stdc++.h>
using namespace std;

int main(int, char**)
{
    int n,m;
    cin >> n >> m;
    vector<vector<int>> matrix(n, vector<int>(m,0));
    for(int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> matrix[i][j];
        }
    }

    vector<int> left2right(100001,0); // for every left border says the farest right one
    for (int j = 0; j < m; ++j) {
        int i = 1;
        int l = 0, start = 0;
        while (i <= n) {
            if (i < n && matrix[i-1][j] <= matrix[i][j]) {
               ++l;
            } else {
                if (l != 0) {
                    for (int s = start; s <= start + l; ++s) {
                        left2right[s] = max(left2right[s], start+l);
                    }
                }
                start = i;
                l = 0;
            }
            ++i;
        }
    }

    int k = 0;
    cin >> k;
    while(k > 0) {
        int l, r;
        cin >> l >> r;
        if (l == r) {
            cout << "Yes\n";
            --k;
            continue;
        }
        --l; --r;
        bool res = left2right[l] >= r;
        if (res)
            cout << "Yes\n";
        else
            cout << "No\n";

        --k;
    }
    return 0;
}