Cod sursa(job #3375257)

Utilizator alexm749Musat Alexandru Nicolae alexm749 Data 11 noiembrie 2026 11:25:58
Problema Struti Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("struti.in");

ofstream g("struti.out");

int n,m,p,x,y,dfmn,nr;
vector<vector<int>>a;
vector<pair<int,int>>v;

struct punct
{
    int i, j, val;
};


deque<punct>dqmx,dqmn;

bool apartf(int is, int js, int i, int j)
{
    int ij=is+x-1,jj=js+y-1;
    return (i>=is&&i<=ij&&j>=js&&j<=jj);
}

int veriff(int is, int js) //coloane -> linii
{
    while(!dqmn.empty()&&!apartf(is,js,dqmn.front().i,dqmn.front().j))dqmn.pop_front();
    while(!dqmx.empty()&&!apartf(is,js,dqmx.front().i,dqmx.front().j))dqmx.pop_front();
    for(int j=js;j<=js+y-1;j++)
    {
        for(int i=is;i<=is+x-1;i++)
        {
            while(!dqmn.empty()&&dqmn.back().val>=a[i][j])dqmn.pop_back();
            dqmn.push_back({i,j,a[i][j]});
            while(!dqmx.empty()&&dqmx.back().val<=a[i][j])dqmx.pop_back();
            dqmx.push_back({i,j,a[i][j]});
        }
    }
    return dqmx.front().val-dqmn.front().val;
}

int main()
{
    f>>n>>m>>p;
    a.resize(n+1);
    for(int i=1;i<=n;i++)a[i].resize(m+1);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)f>>a[i][j];
    }
    /*for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)cout<<a[i][j]<<" ";cout<<'\n';
    }*/
    for(int i=1;i<=p;i++)
    {
        int x,y;
        f>>x>>y;
        v.push_back(make_pair(x,y));
    }
    /*for(int i=0;i<p;i++)
    {
        cout<<v[i].first<<" "<<v[i].second;cout<<'\n';
    }*/
    for(int k=0;k<p;k++)
    {
        dfmn=(1LL<<31)-1;
        //cout<<dfmn;
        x=v[k].first;y=v[k].second;
        for(int ifr=1;ifr<=n-x+1;ifr++)
        {
            for(int jf=1;jf<=m-y+1;jf++)
            {
                int df=veriff(ifr,jf);
                if(df<dfmn){dfmn=df;nr=1;}
                else if(df==dfmn)nr++;
            }
        }
        if(x!=y){x=x^y;y=x^y;x=x^y;
        for(int ifr=1;ifr<=n-x+1;ifr++)
        {
            for(int jf=1;jf<=m-y+1;jf++)
            {
                int df=veriff(ifr,jf);
                if(df<dfmn){dfmn=df;nr=1;}
                else if(df==dfmn)nr++;
            }
        }}
        g<<dfmn<<" "<<nr<<'\n';
    }
    return 0;
}