Cod sursa(job #2479911)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 24 octombrie 2019 17:57:42
Problema Struti Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.56 kb
#include <bits/stdc++.h>

FILE *in = fopen("struti.in", "r"), *out = fopen("struti.out", "w") ;

const int MV = 1e3 ;

int n, m, querys ;
int mat[MV + 2][MV + 2] ;
int minim[MV + 2][MV + 2] ;
int maxim[MV + 2][MV + 2] ;
int ans(1e9) ;
int aparitii ;

void update(int len_x) {
        int i, j ;
        std::deque<int> dq_maxim ;
        std::deque<int> dq_minim ;
        for (j = 1 ; j <= m ; ++ j) {
                dq_maxim.clear() ;
                dq_minim.clear() ;
                for (i = 1 ; i <= n ; ++ i) {
                        if (!dq_maxim.empty() && i - dq_maxim.back() + 1 > len_x) {
                                dq_maxim.pop_back() ;
                        }
                        while (!dq_maxim.empty() && mat[dq_maxim.front()][j] < mat[i][j]) {
                                dq_maxim.pop_front() ;
                        }
                        dq_maxim.push_front(i) ;
                        maxim[i][j] = mat[dq_maxim.back()][j] ;

                        if (!dq_minim.empty() && i - dq_minim.back() + 1 > len_x) {
                                dq_minim.pop_back() ;
                        }
                        while (!dq_minim.empty() && mat[dq_minim.front()][j] > mat[i][j]) {
                                dq_minim.pop_front() ;
                        }
                        dq_minim.push_front(i) ;
                        minim[i][j] = mat[dq_minim.back()][j] ;
                }
        }
}

void solve(int len_x, int len_y) {
        update(len_x) ;
        int i, j, aux1, aux2 ;
        std::deque<int> dq_maxim ;
        std::deque<int> dq_minim ;
        for (i = len_x ; i <= n ; ++ i) {
                dq_maxim.clear() ;
                dq_minim.clear() ;
                for (j = 1 ; j <= m ; ++ j) {
                        if (!dq_maxim.empty() && j - dq_maxim.back() + 1 > len_y) {
                                dq_maxim.pop_back() ;
                        }
                        while (!dq_maxim.empty() && maxim[i][dq_maxim.front()] < maxim[i][j]) {
                                dq_maxim.pop_front() ;
                        }
                        dq_maxim.push_front(j) ;

                        if (!dq_minim.empty() && j - dq_minim.back() + 1 > len_y) {
                                dq_minim.pop_back() ;
                        }
                        while (!dq_minim.empty() && minim[i][dq_minim.front()] > minim[i][j]) {
                                dq_minim.pop_front() ;
                        }
                        dq_minim.push_front(j) ;

                        aux1 = maxim[i][dq_maxim.back()] ;
                        aux2 = minim[i][dq_minim.back()] ;

                        if (j >= len_y && ans > aux1 - aux2) {
                                ans = aux1 - aux2 ;
                                aparitii = 1 ;
                        } else if (j >= len_y && ans == aux1 - aux2) {
                                aparitii ++ ;
                        }
                }
        }
}

int main() {
        fscanf(in, "%d %d %d", &n, &m, &querys) ;
        int i, j, dx, dy ;
        for (i = 1 ; i <= n ; ++ i) {
                for (j = 1 ; j <= m ; ++ j) {
                        fscanf(in, "%d", &mat[i][j]) ;
                }
        }
        while (querys --) {
                fscanf(in, "%d %d", &dx, &dy) ;
                solve(dx, dy) ;
                if (dx != dy) solve(dy, dx) ;
                fprintf(out, "%d %d\n", ans, aparitii) ;
                ans = 1e9 ;
                aparitii = 0 ;
        }
}