Pagini recente » Cod sursa (job #178205) | Cod sursa (job #3207991) | Cod sursa (job #544154) | Cod sursa (job #416029) | Cod sursa (job #3157492)
/*
ID: teparuf1
TASK: dualpal
LANG: C++
*/
#include <bits/stdc++.h>
#define MOD 1000000007
typedef long long int ll;
using namespace std;
ifstream fin("struti.in");
ofstream fout("struti.out");
int n,m,q;
int a[1001][1001];
int mxc[1001][1001],mnc[1001][1001];
int amin=INT_MAX,cnt=0;
void query(int x,int y)
{
for(int j=1;j<=m;j++)
{
deque<int> Q1,Q2;
for(int i=1;i<=x;i++)
{
while(!Q1.empty() && a[Q1.back()][j] > a[i][j])Q1.pop_back();
Q1.push_back(i);
while(!Q2.empty() && a[Q2.back()][j] < a[i][j])Q2.pop_back();
Q2.push_back(i);
}
mnc[x][j]=a[Q1.front()][j];
mxc[x][j]=a[Q2.front()][j];
for(int i=x+1;i<=n;i++)
{
while(!Q1.empty() && a[Q1.back()][j] > a[i][j])Q1.pop_back();
Q1.push_back(i);
while(!Q1.empty() && Q1.front() < i-x+1)Q1.pop_front();
mnc[i][j]=a[Q1.front()][j];
while(!Q2.empty() && a[Q2.back()][j] < a[i][j])Q2.pop_back();
Q2.push_back(i);
while(!Q2.empty() && Q2.front() < i-x+1)Q2.pop_front();
mxc[i][j]=a[Q2.front()][j];
}
}
for(int i=x;i<=n;i++)
{
deque<int> Q1,Q2;
int mx[1001],mn[1001];
for(int j=1;j<=y;j++)
{
while(!Q1.empty() && mnc[i][Q1.back()] > mnc[i][j])Q1.pop_back();
Q1.push_back(j);
while(!Q2.empty() && mxc[i][Q2.back()] < mxc[i][j])Q2.pop_back();
Q2.push_back(j);
}
mn[y]=mnc[i][Q1.front()];
mx[y]=mxc[i][Q2.front()];
for(int j=y+1;j<=m;j++)
{
while(!Q1.empty() && mnc[i][Q1.back()] > mnc[i][j])Q1.pop_back();
Q1.push_back(j);
while(!Q1.empty() && Q1.front() < j-y+1)Q1.pop_front();
mn[j]=mnc[i][Q1.front()];
while(!Q2.empty() && mxc[i][Q2.back()] < mxc[i][j])Q2.pop_back();
Q2.push_back(j);
while(!Q2.empty() && Q2.front() < j-y+1)Q2.pop_front();
mx[j]=mxc[i][Q2.front()];
}
for(int j=y;j<=m;j++)
{
if(mx[j]-mn[j] == amin)cnt++;
if(mx[j]-mn[j] < amin)amin=mx[j]-mn[j],cnt=1;
}
}
}
void solve(int x,int y)
{
query(x,y);
if(x!=y)query(y,x);
fout << amin << " " << cnt << '\n';
amin=INT_MAX,cnt=0;
}
int main()
{
fin >> n >> m >> q;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)fin >> a[i][j];
}
while(q--)
{
int a,b;
fin >> a >> b;
solve(a,b);
}
}