oj.uz

Submission #534564

# Submission time Handle Problem Language Result Execution time Memory
534564 2022-03-08T10:04:56 Z ioi The Kingdom of JOIOI (JOI17_joioi) C++14
100 / 100
 1497 ms 227552 KB 
#include<bits/stdc++.h>

using namespace std;

#define debug(x) cout << '[' << #x << " is: " << x << "] " << endl;
#define inF freopen("6in.txt" , "r" , stdin);
#define outF freopen("6.txt" , "w" , stdout);
#define imod(a , n) (a % n + n ) % n
#define sor(v) sort(v.begin() , v.end());
#define print(v) for(auto f : v ) cout << f << " " ;
#define rsor(v) sort(v.rbegin() , v.rend());
#define rev(v) reverse(v.begin() , v.end());
#define scan(v)for(auto &it : v)cin >> it ;
#define ll long long
#define int ll
#define logar(x , y) log(x) / log(y)
#define __sum(n) n * (n + 1) / 2
#define __lcm(a , b) a / __gcd(a , b) * b
#define pii pair<int , int >
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);
const int N =  2e3 + 5 ;


int n , m ;
int arr[N][N] , arr2[N][N];
int themax[N][N] , themin[N][N] , rmax[N][N] , rmin[N][N];

void process(){


    for(int c = 0 ; c <m ; c ++){
        for(int r = 0 ; r < n ; r ++){

            themax[r][c] = themin[r][c] = arr[r][c];

            if(r)themax[r][c] = max(themax[r][c] , themax[r - 1][c]) , themin[r][c] = min(themin[r][c] , themin[r - 1][c]);

        }
    }


    for(int c = 0 ; c < m ; c ++){

        rmin[n][c] = 1e9 , rmax[n][c] = 0 ;


        for(int r = n - 1 ; r >= 0 ; r --){

            rmin[r][c] = rmax[r][c] = arr[r][c] ;

            rmin[r][c] = min(rmin[r][c] , rmin[r + 1][c]) , rmax[r][c] = max(rmax[r][c] , rmax[r + 1][c]);


        }


    }

}
int mnmm = 1e9 ;

bool check(int number){


    int mx = 0 , mn = 1e9 ;
    int en = n ;
    for(int c = 0 ; c < m; c ++){



        int l = 0 , r = en - 1 , md , ans = n;




        while(l <= r ){

            md = (l + r) / 2 ;



            if(themax[md][c] > number)
                ans = md , r = md - 1 ;
            else l = md + 1 ;




        }
        en = min(en , ans);


         mx = max(mx , rmax[en][c] ), mn = min(mn , rmin[en][c]);





    }


    return mx - mn <= number - mnmm;

}

int32_t main()
{   //inF;
    //inF;outF;
    fastio;


    cin >> n >>m;


    for(int i = 0 ;i < n ; i ++)
        for(int j = 0 ; j < m ; j ++){
        cin >> arr[i][j];
        mnmm = min(mnmm , arr[i][j]);
       // debug(mnmm)

        arr2[i][j] = arr[i][j] ;

    }


   // debug(mnmm)

    int mnans = 1e9 ;



    for(int c = 0 ; c < 4 ; c ++){


        process();

       // cout << "   NEW   \n";



        int l = 0 , r = 1e9 , md ;

        while(l <= r ){


            md = (l + r) / 2 ;



            if(check(md + mnmm))mnans = min(mnans , md) , r = md - 1 ;
            else l = md + 1;



        }
     //   break;


        if(c != 1){

            for(int col = 0 ; col < m ; col ++){

                for(int r = 0 ; r < n ; r ++){


                    arr[r][col] = arr2[r][m - 1 - col];
                }

            }


        }
        else {



            for(int r = 0 ; r < n ; r ++){

                for(int col = 0 ; col < m ; col ++)
                    arr[r][col] = arr2[n - r - 1][col];
            }


          //  cout << endl ;
        }



       // cout << "  NEW  " << c << " \n";



    for (int i = 0; i < n; ++ i){
        for (int j = 0; j < m; ++ j){
           // cout << arr[i][j] << " " ;
            arr2[i][j] = arr[i][j];
        }
           // cout << endl ;
    }


          //  debug(mnans)
        }








   // cout << 11 ;
    cout << mnans ;


}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 532 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 580 KB Output is correct
13 Correct 1 ms 572 KB Output is correct
14 Correct 1 ms 460 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 532 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 580 KB Output is correct
13 Correct 1 ms 572 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 716 KB Output is correct
16 Correct 7 ms 6988 KB Output is correct
17 Correct 7 ms 7244 KB Output is correct
18 Correct 12 ms 7244 KB Output is correct
19 Correct 8 ms 7244 KB Output is correct
20 Correct 8 ms 6468 KB Output is correct
21 Correct 10 ms 7364 KB Output is correct
22 Correct 13 ms 7288 KB Output is correct
23 Correct 8 ms 7372 KB Output is correct
24 Correct 8 ms 6604 KB Output is correct
25 Correct 11 ms 7364 KB Output is correct
26 Correct 8 ms 7372 KB Output is correct
27 Correct 10 ms 7416 KB Output is correct
28 Correct 10 ms 7396 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 532 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 580 KB Output is correct
13 Correct 1 ms 572 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 716 KB Output is correct
16 Correct 7 ms 6988 KB Output is correct
17 Correct 7 ms 7244 KB Output is correct
18 Correct 12 ms 7244 KB Output is correct
19 Correct 8 ms 7244 KB Output is correct
20 Correct 8 ms 6468 KB Output is correct
21 Correct 10 ms 7364 KB Output is correct
22 Correct 13 ms 7288 KB Output is correct
23 Correct 8 ms 7372 KB Output is correct
24 Correct 8 ms 6604 KB Output is correct
25 Correct 11 ms 7364 KB Output is correct
26 Correct 8 ms 7372 KB Output is correct
27 Correct 10 ms 7416 KB Output is correct
28 Correct 10 ms 7396 KB Output is correct
29 Correct 1253 ms 181724 KB Output is correct
30 Correct 1284 ms 191080 KB Output is correct
31 Correct 1325 ms 190996 KB Output is correct
32 Correct 1393 ms 191168 KB Output is correct
33 Correct 1174 ms 168024 KB Output is correct
34 Correct 1418 ms 191332 KB Output is correct
35 Correct 1497 ms 196780 KB Output is correct
36 Correct 1315 ms 221280 KB Output is correct
37 Correct 1467 ms 227552 KB Output is correct