Submission #689500

#	Time	Username	Problem	Language	Result	Execution time	Memory
689500		vicious	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	169 ms	16156 KiB

joioi

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define si second
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
template<typename T> bool chmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int N=2010,INF=2e9;
int h,w,a[N][N],t[N][N];
int gmin=INF,gmax;

void rotate() {
    memset(t,0,sizeof t);
    for (int i = 1; i <= h; ++i) {
        for (int j = 1; j <= w; ++j) {
            t[j][h-i+1]=a[i][j];
        }
    }
    for (int i = 1; i <= w; ++i) {
        for (int j = 1; j <= h; ++j) {
            a[i][j]=t[i][j];
        }
    }
}

bool testmn(int ans) {
    vector<vector<int>> mn(h+10,vector<int>(w+10,INF));
    for (int i = 1; i <= w; ++i) {
        for (int j = h; j >= 1; --j) {
            mn[j][i]=min(mn[j+1][i],a[j][i]);
        }
    }
    vector<int> stop(h+1);
    int r=1,c=1;
    while (1) {
        while (c<=w&&mn[r][c]>=gmax-ans) {
            stop[r]=c++;
        }
        if (c>w) break;
        while (r<=h&&mn[r][c]<gmax-ans) {
            stop[r++]=c-1;
        }
        if (r>h) break;
    }
    int mx = 0;
    for (int i = 1; i <= h; ++i) {
        for (int j = w; j >= 1; --j) {
            if (j==stop[i]) break;
            chmax(mx,a[i][j]);
        }
    }
    return (mx<=gmin+ans);
}

bool testmx(int ans) {
    vector<vector<int>> mx(h+10,vector<int>(w+10));
    for (int i = 1; i <= w; ++i) {
        for (int j = h; j >= 1; --j) {
            mx[j][i]=max(mx[j+1][i],a[j][i]);
        }
    }
    vector<int> stop(h+1);
    int r=1,c=1;
    while (1) {
        while (c<=w&&mx[r][c]<=gmin+ans) {
            stop[r]=c++;
        }
        if (c>w) break;
        while (r<=h&&mx[r][c]>gmin+ans) {
            stop[r++]=c-1;
        }
        if (r>h) break;
    }
    int mn = INF;
    for (int i = 1; i <= h; ++i) {
        for (int j = w; j >= 1; --j) {
            if (j==stop[i]) break;
            chmin(mn,a[i][j]);
        }
    }
    return (mn>=gmax-ans);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin.exceptions(ios::badbit|ios::failbit);
    cin >> h >> w;
    for (int i = 1; i <= h; ++i) {
        for (int j = 1; j <= w; ++j) {
            cin >> a[i][j];
            chmin(gmin,a[i][j]);
            chmax(gmax,a[i][j]);
        }
    }
    ll lo = 0, hi = 1e9+1;
    while (lo+1<hi) {
        ll mid = (lo+hi)>>1ll;
        bool ok = false;
        for (int i = 0; i < 3; ++i) {
            ok|=testmx(mid);
            ok|=testmn(mid);
            rotate();
        }
        ok|=testmx(mid);
        ok|=testmn(mid);
        if (ok) hi = mid;
        else lo = mid;
    }
    cout << hi;
    return 0;
}

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