Submission #241280

#	Time	Username	Problem	Language	Result	Execution time	Memory
241280		aggu_01000101	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1314 ms	180508 KiB

joioi

#include <bits/stdc++.h>
#define int long long
#define mid(l, u) ((l+u)/2)
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
#define INF 100000000000
using namespace std;
const int N = 2005;
int n, m;
int mat[N][N];
pair<int, int> pmm[N][N];
int ourmin, ourmax;
int ind[N];
int ans = 0;
int mini = INF, maxi = -INF;
set<int> el;
vector<int> dist;
void calcpmm(){
    for(int i =0 ;i<n;i++){
        pmm[i][m-1] = {mat[i][m-1], mat[i][m-1]};
        for(int j = m-2;j>=0;j--){
            pmm[i][j].first = min(mat[i][j], pmm[i][j+1].first);
            pmm[i][j].second = max(mat[i][j], pmm[i][j+1].second);
        }
    }
}
int findinrange(int l, int u){
    int theirmin = INF;
    int theirmax = -INF;
    ourmin = INF;
    ourmax = -INF;
    int prevj = m;
    for(int i =0 ;i<n;i++){
        int j = 0;
        for (; (j < prevj) && (mat[i][j] >= l) && (mat[i][j] <= u); j++) {
            ourmin = min(mat[i][j], ourmin);
            ourmax = max(ourmax, mat[i][j]);
        }
        prevj = j;
        if(j<m){
            theirmin = min(pmm[i][j].first, theirmin);
            theirmax = max(pmm[i][j].second, theirmax);
        }
    }
    if(ourmin > ourmax || theirmin > theirmax) return INF;
    return max(theirmax - theirmin, ourmax - ourmin);
}
int findans(){
    calcpmm();
    int tr = INF;
    int lo = 0;
    int hi = maxi - mini;
    while(lo<=hi){
        int mid = mid(lo, hi);
        int temp = findinrange(mini, mini + mid);
        int temp1 = findinrange(maxi - mid, maxi);
        int tocons = min(temp, temp1);
        //cout<<mid<<" "<<temp<<" "<<temp1<<" "<<mini<<" "<<maxi<<endl;
        if(tocons <= mid){
            tr = min(tr, tocons);
            hi = mid-1;
        }
        else lo = mid + 1;
    }
    return tr;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m;
    int a[n][m];
    for(int i =0 ;i<n;i++){
        for(int j = 0;j<m;j++) {
            cin >> mat[i][j];
            maxi = max(maxi, mat[i][j]);
            mini = min(mini, mat[i][j]);
            a[i][j] = mat[i][j];
            dist.push_back(mat[i][j]);
        }
    }
    sort(dist.begin(), dist.end());
    ans = maxi - mini;
    ans = min(ans, findans());
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++) mat[i][j] = a[i][m-j-1];
    }
    //cout<<"INVERTED"<<endl;
    ans = min(ans, findans());
    /*for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++) mat[i][j] = a[n-i-1][m-j-1];
    }
    ans = min(ans, findans());
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++) mat[i][j] = a[n-i-1][j];
    }
    ans = min(ans, findans());*/
    cout<<ans<<endl;
}
/*

4 4
1 12 6 11
11 10 2 14
10 1 9 20
4 17 19 10


8 6
23 23 10 11 16 21
15 26 19 28 19 20
25 26 28 16 15 11
11 8 19 11 15 24
14 19 15 14 24 11
10 8 11 7 6 14
23 5 19 23 17 17
18 11 21 14 20 16
 */

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