Submission #484707

#	Time	Username	Problem	Language	Result	Execution time	Memory
484707		Haruto810198	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	729 ms	187576 KiB

joioi

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = 2147483647;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 2010;

int n, m;
int arr[MAX][MAX];
int pmax[MAX][MAX], pmin[MAX][MAX], smax[MAX][MAX], smin[MAX][MAX];
int gmax, gmin;

bool check(int lmin, int lmax, int rmin, int rmax){
	
	//bool owo = 0;
	//if(lmin == 5 and lmax == 23 and rmin == 10 and rmax == 28) owo = 1;
	
	bool ret = 0;
	
	int ptr = m;
	int curmin = INF, curmax = -INF;
	FOR(i, 1, n, 1){
		while(pmin[i][ptr] < lmin or lmax < pmax[i][ptr]){
			ptr--;
			assert(ptr >= 0);
		}
		curmin = min(curmin, smin[i][ptr + 1]);
		curmax = max(curmax, smax[i][ptr + 1]);
		//if(owo) cerr<<"i = "<<i<<" : ptr = "<<ptr<<endl;
	}
	
	if(rmin <= curmin and curmax <= rmax) ret = 1;
	
	ptr = m;
	curmin = INF, curmax = -INF;
	for(int i = n; i >= 1; i--){
		while(pmin[i][ptr] < lmin or lmax < pmax[i][ptr]){
			ptr--;
			assert(ptr >= 0);
		}
		curmin = min(curmin, smin[i][ptr + 1]);
		curmax = max(curmax, smax[i][ptr + 1]);
		//if(owo) cerr<<"i = "<<i<<" : ptr = "<<ptr<<endl;
	}

	if(rmin <= curmin and curmax <= rmax) ret = 1;
	
	return ret;

}

bool CHECK(int T){
	return (check(gmin, gmin + T, gmax - T, gmax) or check(gmax - T, gmax, gmin, gmin + T));
}

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	
	cin>>n>>m;
	FOR(i, 1, n, 1){
		FOR(j, 1, m, 1){
			cin>>arr[i][j];
		}
	}
	
	//cerr<<"ok"<<endl;
	
	gmax = -INF;
	gmin = INF;
	FOR(i, 1, n, 1){
		pmax[i][0] = -INF;
		pmin[i][0] = INF;
		FOR(j, 1, m, 1){
			pmax[i][j] = max(pmax[i][j-1], arr[i][j]);
			pmin[i][j] = min(pmin[i][j-1], arr[i][j]);
			gmax = max(gmax, arr[i][j]);
			gmin = min(gmin, arr[i][j]);
		}
		
		smax[i][m+1] = -INF;
		smin[i][m+1] = INF;
		for(int j = m; j >= 1; j--){
			smax[i][j] = max(smax[i][j+1], arr[i][j]);
			smin[i][j] = min(smin[i][j+1], arr[i][j]);
		}
	}
	
	//cerr<<"ok"<<endl;

	int L = 0, R = gmax - gmin, mid;
	while(L < R){
		mid = (L + R) / 2;
		if(CHECK(mid)) R = mid;
		else L = mid + 1;
		//cerr<<"CHECK("<<mid<<") = "<<CHECK(mid)<<endl;
	}
	
	cout<<L<<'\n';
	
    return 0;

}

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