by hansang:

#include<bits/stdc++.h>
using namespace std;
const int N=260;
int q1[N], q2[N], a[N][N], f1[N][N], f2[N][N]; //1small,2big
int main(){
    int n, m, K; scanf("%d%d%d", &n, &m, &K);
    for(int i=1; i<=n; i++) 
        for(int j=1; j<=n; j++) scanf("%d", &a[i][j]);
    memset(f1, 0x3f, sizeof(f1));
    memset(f2, 0, sizeof(f2));
    for(int i=1; i<=n; i++){
        int l1=1, r1=0, l2=1, r2=0;
        for(int j=1; j<=n; j++){
            int t=max(1, j-m+1);
            while(l1<=r1 && q1[l1]<=j-m) l1++;
            while(l1<=r1 && a[i][q1[r1]]>=a[i][j]) r1--;
            q1[++r1]=j; f1[i][t]=min(f1[i][t], a[i][q1[l1]]);
            
            while(l2<=r2 && q2[l2]<=j-m) l2++;
            while(l2<=r2 && a[i][q2[r2]]<=a[i][j]) r2--;
            q2[++r2]=j; f2[i][t]=max(f2[i][t], a[i][q2[l2]]);
        }
    }
    for(int i=1; i<=K; i++){
        int l, r; scanf("%d%d", &l, &r);
        int s1=N, s2=0;
        for(int j=l; j<=l+m-1; j++){
            s1=min(s1, f1[j][r]);
            s2=max(s2, f2[j][r]);
        }
        printf("%d\n", s2-s1);
    }
    return 0;
}

by hansang:

#include<bits/stdc++.h>
using namespace std;
const int N=260;
int q1[N], q2[N], a[N][N], f1[N][N], f2[N][N]; //1small,2big
int main(){
	int n, m, K; scanf("%d%d%d", &n, &m, &K);
	for(int i=1; i<=n; i++) 
		for(int j=1; j<=n; j++) scanf("%d", &a[i][j]);
	memset(f1, 0x3f, sizeof(f1));
	memset(f2, 0, sizeof(f2));
	for(int i=1; i<=n; i++){
		int l1=1, r1=0, l2=1, r2=0;
		for(int j=1; j<=n; j++){
			int t=max(1, j-m+1);
			while(l1<=r1 && q1[l1]<=j-m) l1++;
			while(l1<=r1 && a[i][q1[r1]]>=a[i][j]) r1--;
			q1[++r1]=j; f1[i][t]=min(f1[i][t], a[i][q1[l1]]);
			
			while(l2<=r2 && q2[l2]<=j-m) l2++;
			while(l2<=r2 && a[i][q2[r2]]<=a[i][j]) r2--;
			q2[++r2]=j; f2[i][t]=max(f2[i][t], a[i][q2[l2]]);
		}
	}
	for(int i=1; i<=K; i++){
		int l, r; scanf("%d%d", &l, &r);
		int s1=N, s2=0;
		for(int j=l; j<=l+m-1; j++){
			s1=min(s1, f1[j][r]);
			s2=max(s2, f2[j][r]);
		}
		printf("%d\n", s2-s1);
	}
	return 0;
}