Cod sursa(job #3367916)

Utilizator Andrei1209Andrei Mircea Andrei1209 Data 12 octombrie 2026 10:16:22
Problema Struti Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.86 kb
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;
}