Cod sursa(job #2545210)

Utilizator AndreiD31Dragan Andrei AndreiD31 Data 12 februarie 2020 21:35:44
Problema Struti Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f("struti.in");
ofstream g("struti.out");

deque <int> qM,qm,qfM,qfm;
int n,m,t,A,B,i,minim,nr,j,dif,maxi[1010][1010],mini[1010][1010],a[1010][1010];

void afla_minim()
{
    for(j=1; j<=m; j++)
    {
        qM.clear();
        qm.clear();

        for(i=1; i<=n; i++)
        {
            while(!qM.empty() && a[i][j]>=a[qM.back()][j])qM.pop_back();
            qM.push_back(i);
            while(i-qM.front()>=A)qM.pop_front();
            maxi[i][j]=a[qM.front()][j];

            while(!qm.empty() && a[i][j]<=a[qm.back()][j])qm.pop_back();
            qm.push_back(i);
            while(i-qm.front()>=A)qm.pop_front();
            mini[i][j]=a[qm.front()][j];
        }
    }

    for(i=A; i<=n; i++)
    {
        qfM.clear();
        qfm.clear();

        for(j=1; j<=m; j++)
        {
            while(!qfM.empty() && maxi[i][j]>=maxi[i][qfM.back()])qfM.pop_back();
            qfM.push_back(j);
            while(j-qfM.front()>=B)qfM.pop_front();

            while(!qfm.empty() && mini[i][j]<=mini[i][qfm.back()])qfm.pop_back();
            qfm.push_back(j);
            while(j-qfm.front()>=B)qfm.pop_front();

            if(i>=A && j>=B)
            {
                dif=maxi[i][qfM.front()]-mini[i][qfm.front()];
                if(dif<minim)
                {
                    minim=dif;
                    nr=1;
                }
                else if(dif==minim)nr++;
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    f.tie(NULL);
    g.tie(NULL);

    f>>n>>m>>t;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            f>>a[i][j];
        }
    }

    for(int caz=1; caz<=t; caz++)
    {
        f>>A>>B;
        minim=INT_MAX;

        afla_minim();
        if(A!=B)
        {
            swap(A,B);
            afla_minim();
        }

        g<<minim<<" "<<nr<<'\n';
    }
    return 0;
}