Submission #1157749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157749		koukirocks	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	470 ms	31920 KiB

joioi

#include<bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define F first 
#define S second

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<class T>
using vvector = vector<vector<T>>;
const int INF = 0x3f3f3f3f;

bool check(int w,int h,int d,vector<pll> &rg1,vector<pll> &rg2) {
    
}

bool ok(int h,int w,vvector<ll> &a,int mn,int mx,ll x) {
    vector<pll> rg1(h+1,{INF,0}),rg2(h+1,{INF,0});
    for (int i=1;i<=h;i++) {
        for (ll j=1;j<=w;j++) {
            if (a[i][j]>mn+x) {
                rg2[i].F=min(j,rg2[i].F);
                rg2[i].S=max(j,rg2[i].S);
            }   
            if (a[i][j]<mx-x) {
                rg1[i].F=min(j,rg1[i].F);
                rg1[i].S=max(j,rg1[i].S);
            }
        }
        if (!(rg1[i].S<rg2[i].F or rg2[i].S<rg1[i].F)) return false;
    }
    bool flagd1=true;
    ll now=w;
    for (int i=1;i<=h;i++) {
        now=min(now,rg2[i].F-1);
        if (now<rg1[i].S) {
            flagd1=false;
            break;
        }
    }
    bool flagd2=true;
    now=w;
    for (int i=1;i<=h;i++) {
        now=min(now,rg1[i].F-1);
        if (now<rg2[i].S) {
            flagd2=false;
            break;
        }
    }
    // cout<<flagd<<" fd\n";
    bool flaga1=true;
    now=0;
    for (int i=1;i<=h;i++) {
        now=max(now,rg1[i].S);
        if (rg2[i].F<=now) {
            flaga1=false;
            break;
        }
    }
    bool flaga2=true;
    now=0;
    for (int i=1;i<=h;i++) {
        now=max(now,rg2[i].S);
        if (rg1[i].F<=now) {
            flaga2=false;
            break;
        }
    }
    // cout<<flaga<<" fa\n";
    return flaga1 or flagd1 or flaga2 or flagd2;
}

int main() {
    speed;
    ll h,w;
    cin>>h>>w;
    vvector<ll> a(h+1,vector<ll>(w+1));
    ll mn=INF,mx=0;
    for (int i=1;i<=h;i++) {
        for (int j=1;j<=w;j++) {
            cin>>a[i][j];
            mx=max(mx,a[i][j]);
            mn=min(mn,a[i][j]);
        }
    }
    ll l=0,r=INF;
    while (l<r) {
        int mid=l+r>>1;
        if (ok(h,w,a,mn,mx,mid)) r=mid;
        else l=mid+1;
    }
    cout<<l<<"\n";
    return 0;
}

/*
4 4
1 1 1 1
5 5 5 5
1 1 1 1
1 1 1 1
*/

Compilation message (stderr)

joioi.cpp: In function 'bool check(int, int, int, std::vector<std::pair<long long int, long long int> >&, std::vector<std::pair<long long int, long long int> >&)':
joioi.cpp:17:1: warning: no return statement in function returning non-void [-Wreturn-type]
   17 | }
      | ^

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