Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int m, n, a[555][555];

int main()
{
    int Q, aLow, aHigh;

    cin >> m >> n >> Q;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", a[i] + j);

    while (Q--)
    {
        scanf("%d%d", &aLow, &aHigh);
        int x = 1, xx = 1, ans = 0;
        for (int D = 2; D <= m + n; D++)
        {
            int minRow = max(1, D - n);
            int maxRow = min(m, D - 1);

            while (x <= maxRow && a[x][D - x] < aLow) x++;
            while (x > minRow && a[x - 1][D - x + 1] >= aLow) x--;

            while (xx >= minRow && a[xx][D - xx] > aHigh) xx--;
            while (xx < maxRow && a[xx + 1][D - xx - 1] <= aHigh) xx++;

            if (x >= minRow && x <= maxRow && xx >= minRow && xx <= maxRow)
                ans = max(ans, xx - x + 1);
        }

        printf("%d\n", ans * ans);
    }
}

Code mẫu của happyboy99x

#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 500+7;
int m, n, a[N][N], q;

void enter() {
    scanf("%d%d%d",&m,&n,&q);
    for(int i = 0; i < m; ++i)
        for(int j = 0; j < n; ++j)
            scanf("%d", &a[i][j]);
}

int query(int low, int high) {
    int res = -1;
    for(int i = m-1; i > res; --i) {
        int l = 0, r = n-1;
        while(l < r) {
            int mid = (l+r) >> 1;
            if(a[i][mid] <= high) r = mid;
            else l = mid+1;
        }
        if(a[i][l] <= high) {
            int lo = res, hi = min(n-1-l, i);
            while(lo < hi) {
                int mid = (lo+hi+1) >> 1;
                if(a[i-mid][l+mid] >= low) lo = mid;
                else hi = mid - 1;
            }
            if(a[i-lo][l+lo] >= low) res = lo;
        }
    }
    return (res+1)*(res+1);
}

void solve() {
    while(q--) {
        int l, r; scanf("%d%d",&l,&r);
        printf("%d\n", query(l, r));
    }
}

int main() {
    enter();
    solve();
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> II;

const int N = 505;
const int M = N + N;
const int MAXQ = 1e4 + 4;

int D[N * N], head[M], tail[M];
II L[MAXQ], R[MAXQ];
int a[N][N];
int ansL[MAXQ], ans[MAXQ];

int n, m, Q, Size;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("GRAPE.txt", "r", stdin);
    freopen("GRAPE.out", "w", stdout);
#endif
    cin >> m >> n >> Q;
    for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) cin >> a[i][j];
    int nDiag = 0;
    for (int j = 1; j <= n; ++j) {
        ++nDiag;
        head[nDiag] = Size + 1;
        for (int x = 1, y = j; x <= m && y > 0; ++x, --y)
            D[++Size] = a[x][y];
        tail[nDiag] = Size;
    }
    for (int i = 2; i <= m; ++i) {
        ++nDiag;
        head[nDiag] = Size + 1;
        for (int x = i, y = n; x <= m && y > 0; ++x, --y)
            D[++Size] = a[x][y];
        tail[nDiag] = Size;
    }
    for (int i = 1; i <= Q; ++i) {
        cin >> L[i].first >> R[i].first;
        L[i].second = R[i].second = i;
    }
    sort(L + 1, L + 1 + Q); sort(R + 1, R + 1 + Q);
    for (int i = 1; i <= nDiag; ++i) {
        int pointer = head[i] - 1;
        for (int j = 1; j <= Q; ++j) {
            while (pointer < tail[i] && D[pointer + 1] < L[j].first) ++pointer;
            ansL[L[j].second] = pointer;
        }
        pointer = head[i] - 1;
        for (int j = 1; j <= Q; ++j) {
            while (pointer < tail[i] && D[pointer + 1] <= R[j].first) ++pointer;
            ans[R[j].second] = max(ans[R[j].second], pointer - ansL[R[j].second]);
        }
    }
    for (int i = 1; i <= Q; ++i) cout << ans[i] * ans[i] << '\n';
    return 0;
}

Code mẫu của RR

#include <sstream>
#include <iomanip>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++)
#define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--)
#define SET(a,v) memset(a,v,sizeof(a))
#define sqr(x) ((x)*(x))
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair

#define DEBUG(x) cout << #x << " = "; cout << x << endl;
#define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl;
#define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl;
using namespace std;

//Buffer reading
int INP,AM,REACHEOF;
#define BUFSIZE (1<<12)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp) { \
        if (REACHEOF) return 0;\
        memset(BUF,0,sizeof BUF);\
        int inpzzz = fread(BUF,1,BUFSIZE,stdin);\
        if (inpzzz != BUFSIZE) REACHEOF = true;\
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading

const long double PI = acos((long double) -1.0);
const int oo = 1000111000;

int a[511][511], l, r, m, n, q;

void solve() {
    int u, v, x, y;
    u = v = x = y = 1;
    if (a[u][v] < l) { ++u; --v; }
    if (a[x][y] > r) { --x; ++y; }

    int res = max(x - u + 1, 0);
    FOR(diag, 2, m+n-1) {
        ++v; if (v > n+1) { ++u; --v; }
        ++x; if (x > m+1) { ++y; --x; }

        if (a[u][v] < l) { ++u; --v; }
        if (a[x][y] > r) { --x; ++y; }

        res = max(res, x - u + 1);
    }

    printf("%d\n", res * res);
}

int main() {
    while (scanf("%d%d%d", &m, &n, &q) == 3) {
        // Hang 0
        FOR(j,0,n+1) a[0][j] = -oo;
        // Cot n+1
        FOR(i,0,m+1) a[i][n+1] = -oo;
        // Hang m+1
        FOR(j,0,n+1) a[m+1][j] = oo;
        // Cot 0
        FOR(i,0,m+1) a[i][0] = oo;

        FOR(i,1,m) FOR(j,1,n) scanf("%d", &a[i][j]);

        while (q--) {
            scanf("%d%d", &l, &r);
            solve();
        }
    }
    return 0;
}

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

#include <ctime>
#include <deque>
#include <bitset>
#include <cctype>
#include <utility>
#include <cassert>

using namespace std;

typedef long long ll;
typedef double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(int i = 0; i < (n); ++i)
#define Repd(i,n) for(int i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(int i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(int i = (a); i >= (b); --i)
#define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
//#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))

template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); }

const int bfsz = 1 << 16;
char bf[bfsz + 5];
int rsz = 0;
int ptr = 0;
char gc() {
    if (rsz <= 0) {
        ptr = 0;
        rsz = (int) fread(bf, 1, bfsz, stdin);
        if (rsz <= 0)
            return EOF;
    }
    --rsz;
    return bf[ptr++];
}
void ga(char &c) {
    c = EOF;
    while (!isalpha(c))
        c = gc();
}
int gs(char s[]) {
    int l = 0;
    char c = gc();
    while (isspace(c))
        c = gc();
    while (c != EOF && !isspace(c)) {
        s[l++] = c;
        c = gc();
    }
    s[l] = '\0';
    return l;
}
template<class T> bool gi(T &v) {
    v = 0;
    char c = gc();
    while (c != EOF && c != '-' && !isdigit(c))
        c = gc();
    if (c == EOF)
        return false;
    bool neg = c == '-';
    if (neg)
        c = gc();
    while (isdigit(c)) {
        v = v * 10 + c - '0';
        c = gc();
    }
    if (neg)
        v = -v;
    return true;
}

typedef pair<int, int> II;

const ld PI = acos(-1.0);
const ld eps = 1e-9;

const int dr[] = {0, +1, 0, -1};
const int dc[] = {+1, 0, -1, 0};

const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
const ll mod = (ll)1e9 + 7;

#define maxn 505

int n, m, a[maxn][maxn], q, L, R, l[maxn], r[maxn];

int  main()
{
//  freopen("in.txt", "r", stdin);
    cin >> n >> m >> q;
    For(i, 1, n) For(j, 1, m) scanf("%d", &a[i][j]);
    For(i, 1, n) {
        a[i][m + 1] = -inf;
        a[i][0] = inf;
    }
    Rep(run, q){
        cin >> L >> R;
        if(R < a[1][m]){
            cout << 0 << endl;
            continue;
        }

        l[0] = 0; r[0] = 0;
        For(i, 1, n){
            r[i] = r[i - 1]; l[i] = l[i - 1];
            while(a[i][r[i]] > R) r[i]++;
            while(a[i][l[i] + 1] >= L) l[i]++;
        }

        int run = 0, res = 0;
        For(i, 1, n){
            if(r[i] > l[i]) continue;
            while(run < n && l[i] - r[run + 1] >= run + 1 - i) run++;
            res = max(res, run - i + 1);
        }

        cout << res * res << endl;

    }

    return 0;
}

Code mẫu của skyvn97

#include<stdio.h>
#define MAX   555
int a[MAX][MAX];
int m,n,q;
void init(void) {
    scanf("%d",&m);
    scanf("%d",&n);
    scanf("%d",&q);
    int i,j;
    for (i=1;i<=m;i=i+1)
        for (j=1;j<=n;j=j+1)
            scanf("%d",&a[i][j]);
}
int min(int a,int b) {
    if (a<b) return (a); else return (b);
}
int fstlow(int x,int l,int r,int val) {
    if (r==l) return (r);
    if (r-l==1) {
        if (a[x][l]<=val) return (l);
        return (r);
    }
    int m=(r+l)/2;
    if (a[x][m]<=val) return(fstlow(x,l,m,val));
    return (fstlow(x,m+1,r,val));
}
int lsthig(int x,int y,int l,int r,int val) {
    if (r==l) return (r);
    if (r-l==1) {
        if (a[x-r+1][y+r-1]>=val) return (r);
        return (l);
    }   
    int m=(r+l)/2;
    if (a[x-m+1][y+m-1]>=val) return (lsthig(x,y,m,r,val));
    return (lsthig(x,y,l,m-1,val));
}
void process(void) {
    int i,j,l,h,b,t,s;
    for (i=1;i<=q;i=i+1) {
        scanf("%d",&l);
        scanf("%d",&h);
        b=0;        
        for (j=m;j>=1;j=j-1) {          
            if (j<=b) break;
            if (a[j][n-b]>h) continue;
            t=fstlow(j,1,n-b,h);            
            if (t+b>n) continue;
            if (a[j-b][t+b]<l) continue;            
            s=lsthig(j,t,b+1,min(j,n-t+1),l);                       
            b=s;
            if (b==min(m,n)) break;
            }
        printf("%d\n",b*b);             
    }
}
int main(void) {
    //freopen("tmp.txt","r",stdin);
    init();
    process();
    return 0;
}