Submission #224717

#	Time	Username	Problem	Language	Result	Execution time	Memory
224717		Ruxandra985	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	3312 ms	120108 KiB

joioi

#include <bits/stdc++.h>
#define DIMN 2010
using namespace std;

int mini , maxi , n , m , sol;
int a[DIMN][DIMN] , where[DIMN][DIMN] , h[DIMN];
priority_queue <pair <int , pair <int,int> > > up , down;
char buff[DIMN * DIMN * 12];
int pos;

int getnr(){
    int nr = 0;

    while ('0' > buff[pos] || buff[pos] > '9')
        pos++;

    while ('0' <= buff[pos] && buff[pos] <= '9'){
        nr = nr * 10 + buff[pos] - '0';
        pos++;
    }

    return nr;

}

void solve(){
    int i , j , maxis , minis , maxij , minij , val , ic , jc;

    /// jos includ mini, sus includ maxi

    for (i = 1 ; i <= n ; ++i)
        memset (where[i] , 0 , sizeof(where[i]));

    for (j = 1 ; j <= m ; ++j){

        for (i = 1 ; i <= n ; ++i){
            if (a[i][j] == mini)
                break;
        }

        h[j] = max(n - i + 1 , h[j - 1]); /// fie iau exact cat trb fie mai mult


        for (i = 1 ; i <= h[j] ; ++i)
            where[n - i + 1][j] = 1; /// apartine tarii de jos

    }

    minij = minis = 2000000000;
    maxij = maxis = -2000000000;

    /// e clar ca toate mini urile sunt jos

    for (i = 1 ; i <= n ; ++i){
        for (j = 1 ; j <= m ; ++j){
            if (where[i][j] == 0){
                minis = min (minis , a[i][j]);
                maxis = max (maxis , a[i][j]);
            }
            else {
                minij = min (minij , a[i][j]);
                maxij = max (maxij , a[i][j]);
            }
        }
    }

    /// daca exista vreun maxi jos, nu e ok

    if (maxij == maxi)
        return;

    /// altfel, toate mini urile sunt jos, toate maxi urile sunt sus

    while (!down.empty())
        down.pop();
    while (!up.empty())
        up.pop();

    for (j = 1 ; j <= m ; ++j){
        if (j == m || h[j] < h[j + 1])
            down.push( make_pair( -a[n - h[j]][j] , make_pair(n - h[j] , j)) );
    }

    /// in down pui candidatii


    for (i = 1 ; i <= n ; ++i){
        for (j = 1 ; j <= m ; ++j){
            if (where[i][j] == 0){
                up.push( make_pair( -a[i][j] , make_pair(i , j)) );
            }
        }
    }

    while (!down.empty()){

        val = -down.top().first;
        ic = down.top().second.first;
        jc = down.top().second.second;

        down.pop();

        /// val = cea mai mica val cu care pot sa extind

        maxij = max(maxij , val);

        if (maxij == maxi)
            return;

        where[ic][jc] = 1;

        h[jc]++;

        if (h[jc - 1] + 1 == h[jc] && jc - 1 != 0 && n - h[jc - 1] > 0)
            down.push( make_pair( -a[n - h[jc - 1]][jc - 1] , make_pair(n - h[jc - 1] , jc - 1)) );

        if ((jc == m || h[jc] != h[jc + 1]) && n - h[jc] > 0)
            down.push( make_pair( -a[n - h[jc]][jc] , make_pair(n - h[jc] , jc)) );

        val = -up.top().first;
        minis = val;
        ic = up.top().second.first;
        jc = up.top().second.second;

        while (where[ic][jc]){
            up.pop();
            if (up.empty())
                break;
            val = -up.top().first;
            ic = up.top().second.first;
            jc = up.top().second.second;
            minis = val;
        }
        if (!up.empty())
            sol = min(sol , max(maxis - minis , maxij - minij));
        else break;
    }


}

int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int i , j , st , dr;

    fread(buff , 1 , DIMN * DIMN * 12 , fin);

    n = getnr();
    m = getnr();


    mini = 2000000000;
    maxi = -2000000000;

    for (i = 1 ; i <= n ; i++){
        for (j = 1 ; j <= m ; j++){
            a[i][j] = getnr();
            mini = min(mini , a[i][j]);
            maxi = max(maxi , a[i][j]);
        }
    }

    sol = maxi - mini;

    solve();

    for (i = 1 ; i <= n ; i++){
        st = 1;
        dr = m;
        while (st < dr){
            swap(a[i][st] , a[i][dr]);
            st++;
            dr--;
        }
    }

    solve();

    for (j = 1 ; j <= m ; j++){
        st = 1;
        dr = n;
        while (st < dr){
            swap(a[st][j] , a[dr][j]);
            st++;
            dr--;
        }
    }

    solve();

    for (i = 1 ; i <= n ; i++){
        st = 1;
        dr = m;
        while (st < dr){
            swap(a[i][st] , a[i][dr]);
            st++;
            dr--;
        }
    }

    solve();

    fprintf (fout,"%d",sol);

    return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:148:10: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     fread(buff , 1 , DIMN * DIMN * 12 , fin);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40