Pagini recente » Borderou de evaluare (job #3367915) | Borderou de evaluare (job #3366884) | Borderou de evaluare (job #3366885) | Borderou de evaluare (job #3368011) | Cod sursa (job #3367916)
fix the compiling errors: #include <fstream>
#include <deque>
using namespace std;
ifstream fin("struti.in");
ofstream fout("struti.out");
const int Nmax = 1005;
int mat[Nmax][Nmax], n, m, solution;
void solve( int dx, int dy )///dx = lungime pe verticala
{
deque<int>colMax[Nmax];
deque<int> colMin[Nmax];
for ( i = 1; i < dx; ++i )
{
for ( j = 1; j <= m; ++j )
{
while ( colMax[j].empty() == false && mat[i][j] > mat[ colMax[j].back() ][j] )
{
colMax.pop_back();
}
colMax.push_back(i);
while ( colMin.empty() == false && mat[i][j] < mat[ colMin[j].back() ][j] )
{
colMin.pop_back();
}
colMin.push_back(i);
}
}
for ( i = dx; i <= n; ++i )
{
for (j = 1; j <= m; ++j )
{
if ( colMax.front() <= i - dx )
colMax.pop_front();
while ( colMax.empty() == false && mat[i][j] > mat[ colMax[j].back() ][j] )
{
colMax.pop_back();
}
colMax.push_back(i);
if ( colMin.front() <= i - dx )
colMin.pop_front();
while ( colMin.empty() == false && mat[i][j] < mat[ colMin[j].back() ][j] )
{
colMin.pop_back();
}
colMin.push_back(i);
}
int v[Nmax];
for ( i = 1; i <= m; ++i )
{
v[i] = mat[colMax[i].back()][i];
}
deque<int>Max, Min;
for ( j = 1; j < dy; ++j )//maxCol[j].back() ----> linia cu cea mai mare val de pe col j
{
while ( !Max.empty() && v[Max.back()] < v[j] )
Max.pop_back();
Max.push_back(j);
while ( !Min.empty() && v[Min.back()] > v[j] )
Min.pop_back();
Min.push_back(j);
}
for ( j = dy; j <= m; ++j )
{
if ( Max.front <= j - dy )
Max.pop_front();
while ( !Max.empty() && v[Max.back()] < v[j] )
Max.pop_back();
Max.push_back(j);
.
if ( Min.front() <= j - dy )
Min.pop_front();
while ( !Min.empty() && v[Min.back()] > v[j] )
Min.pop_back();
Min.push_back(j);
solution = min( solution, v[Max.front()] - v[Min.front()]);
}
}
}
int main()
{
int p;
fin >> n >> m >> p;
int i, j;
for ( i = 1; i <= n; ++i )
for ( j = 1; j <= m; ++j )
fin >> mat[i][j];
for ( i = 1; i <= p; ++i )
{
int dx, dy;
fin >> dx >> dy;
solution = 8000 + 132;
solve(dx, dy);
fout << solution << '\n';
}
return 0;
}