Cod sursa(job #3375356)

Utilizator alexm749Musat Alexandru Nicolae alexm749 Data 11 noiembrie 2026 14:44:01
Problema Struti Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.71 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,mx,mn;
vector<pair<int,int>>v;

deque<pair<int,int>>dq;

void genmn(int x, int y)
{
    for(int i=1; i<=n; i++)
    {
        dq.clear();
        for(int j=1; j<x; j++)
        {
            while(!dq.empty()&&dq.back().first>=a[i][j])dq.pop_back();
            dq.push_back({a[i][j],j});
        }
        for(int j=x; j<=m; j++)
        {
            if(dq.front().second<=j-x)dq.pop_front();
            while(!dq.empty()&&dq.back().first>=a[i][j])dq.pop_back();
            dq.push_back({a[i][j],j});
            mn[i][j-x+1]=dq.front().first;
        }
    }
    for(int j=1; j<=m-x+1; j++)
    {
        dq.clear();
        for(int i=1; i<y; i++)
        {
            while(!dq.empty()&&dq.back().first>=mn[i][j])dq.pop_back();
            dq.push_back({mn[i][j],i});
        }
        for(int i=y; i<=n; i++)
        {
            if(dq.front().second<=i-y)dq.pop_front();
            while(!dq.empty()&&dq.back().first>=mn[i][j])dq.pop_back();
            dq.push_back({mn[i][j],i});
            mn[i-y+1][j]=dq.front().first;
        }
    }
}

void genmx(int x, int y)
{
    for(int i=1; i<=n; i++)
    {
        dq.clear();
        for(int j=1; j<x; j++)
        {
            while(!dq.empty()&&dq.back().first<=a[i][j])dq.pop_back();
            dq.push_back({a[i][j],j});
        }
        for(int j=x; j<=m; j++)
        {
            if(dq.front().second<=j-x)dq.pop_front();
            while(!dq.empty()&&dq.back().first<=a[i][j])dq.pop_back();
            dq.push_back({a[i][j],j});
            mx[i][j-x+1]=dq.front().first;
        }
    }
    for(int j=1; j<=m-x+1; j++)
    {
        dq.clear();
        for(int i=1; i<y; i++)
        {
            while(!dq.empty()&&dq.back().first<=mx[i][j])dq.pop_back();
            dq.push_back({mx[i][j],i});
        }
        for(int i=y; i<=n; i++)
        {
            if(dq.front().second<=i-y)dq.pop_front();
            while(!dq.empty()&&dq.back().first<=mx[i][j])dq.pop_back();
            dq.push_back({mx[i][j],i});
            mx[i-y+1][j]=dq.front().first;
        }
    }
}

int main()
{
    f>>n>>m>>p;
    a.resize(n+1);
    mn.resize(n+1);
    mx.resize(n+1);
    for(int i=1; i<=n; i++)
    {
        a[i].resize(m+1);
        mn[i].resize(m+1,9);
        mx[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<=p; i++)
    {
        int x,y;
        f>>x>>y;
        v.push_back(make_pair(x,y));
    }
    for(int k=0; k<p; k++)
    {
        dfmn=(1LL<<31)-1;
        x=v[k].first;
        y=v[k].second;
        genmn(x,y);
        genmx(x,y);
        for(int i=1; i<=n-y+1; i++)
        {
            for(int j=1; j<=m-x+1; j++)
            {
                int df=mx[i][j]-mn[i][j];
                if(df<dfmn)
                {
                    dfmn=df;
                    nr=1;
                }
                else if(df==dfmn)nr++;
            }
        }
        if(x!=y)
        {
            x=x^y;
            y=x^y;
            x=x^y;
            genmn(x,y);
            genmx(x,y);
            for(int i=1; i<=n-y+1; i++)
            {
                for(int j=1; j<=m-x+1; j++)
                {
                    int df=mx[i][j]-mn[i][j];
                    if(df<dfmn)
                    {
                        dfmn=df;
                        nr=1;
                    }
                    else if(df==dfmn)nr++;
                }
            }
        }
        g<<dfmn<<" "<<nr<<'\n';

    }
    return 0;
}