Cod sursa(job #3375815)

Utilizator ioanxhIoan Budeanu ioanxh Data 13 noiembrie 2026 22:10:11
Problema Struti Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.43 kb
#include<bits/stdc++.h>
#define nl '\n'
using namespace std;
const string file="struti";
ifstream F(file+".in");
ofstream G(file+".out");
//#define F cin
//#define G cout
const int DD=1001;
int n,m,q,v[DD][DD];
int mn[DD][DD],mx[DD][DD];
pair<int,int> solve(int x, int y) {
    deque<int>dmin,dmax;
    int mini=1e9,cnt=0;
    for (int i=1; i<=n; ++i) {
        dmin.clear();
        dmax.clear();
        for (int j=1; j<=m; ++j) {
            while (!dmin.empty() && dmin.front()<=j-y)
                dmin.pop_front();
            while (!dmax.empty() && dmax.front()<=j-y)
                dmax.pop_front();
            while (!dmin.empty() && v[i][dmin.back()]>=v[i][j])
                dmin.pop_back();
            while (!dmax.empty() && v[i][dmax.back()]<=v[i][j])
                dmax.pop_back();
            dmin.push_back(j);
            dmax.push_back(j);
            if (j>=y) {
                mn[i][j-y+1]=v[i][dmin.front()];
                mx[i][j-y+1]=v[i][dmax.front()];
            }
        }
    }
    for (int j=1; j<=m-y+1; ++j) {
        dmin.clear();
        dmax.clear();
        for (int i=1; i<=n; ++i) {
            while (!dmin.empty() && dmin.front()<=i-x)
                dmin.pop_front();
            while (!dmax.empty() && dmax.front()<=i-x)
                dmax.pop_front();
            while (!dmin.empty() && mn[dmin.back()][j]>=mn[i][j])
                dmin.pop_back();
            while (!dmax.empty() && mx[dmax.back()][j]<=mx[i][j])
                dmax.pop_back();
            dmin.push_back(i);
            dmax.push_back(i);
            if (i>=x) {
                int dif=mx[dmax.front()][j]-mn[dmin.front()][j];
                if (dif<mini)
                    mini=dif,cnt=1;
                else if (dif==mini) ++cnt;
            }
        }
    }
    return {mini,cnt};
}
int main(){
    F>>n>>m>>q;
    for (int i=1; i<=n; ++i)
        for (int j=1; j<=m; ++j)
            F>>v[i][j];
    while (q--) {
        int x,y;
        F>>x>>y;
        if (x==y) {
            auto p=solve(x,y);
            G<<p.first<<' '<<p.second<<nl;
        }
        else {
            auto p=solve(x,y);
            auto r=solve(y,x);
            if (p.first<r.first) G<<p.first<<' '<<p.second<<nl;
            else if (r.first<p.first) G<<r.first<<' '<<r.second<<nl;
            else G<<p.first<<' '<<p.second+r.second<<nl;
        }
    }
    system("pause");
    return 0;
}