Submission #321721

#	Time	Username	Problem	Language	Result	Execution time	Memory
321721		Kevin_Zhang_TW	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	2112 ms	63468 KiB

joioi

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template <class T, class ...U> 
void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template <class T>
void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l) == r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

template <class T>
bool chmin(T &a, T b) { return b < a ? (a = b, true) : false; }
template <class T>
bool chmax(T &a, T b) { return a < b ? (a = b, true) : false; }

const int MAX_N = 2010, inf = 1e9;
//#define int ll
int n, m, a[MAX_N][MAX_N], res = inf;
int pfmx[MAX_N][MAX_N];
vector<pair<int,int>> id;
void init() {
	id.reserve(n * m);
	for (int i = 1;i <= n;++i)
		for (int j = 1;j <= m;++j)
			id.pb(i, j);
	sort(AI(id), [&](auto x, auto y) {
			return a[x.first][x.second] < a[y.first][y.second];
			});
}
		
void update() {
	for (int i = 1;i <= n;++i)
		for (int j = 1;j <= m;++j) {
			pfmx[i][j] = max({pfmx[i-1][j], pfmx[i][j-1], a[i][j]});
		}

	auto get = [&](pair<int,int> p) {
		return a[p.first][p.second];
	};

	for (int i = 0, j = 0;i+1 < id.size();++i) {


		auto valid = [&](pair<int,int> p) {
			return pfmx[p.first][p.second] <= get(id[i]);
		};

		while (j <= i && valid(id[j]))
			++j;

		if (valid(id[0]) && valid(id[i]))
			chmin(res, max(get(id[i]) - get(id[0]), get(id.back()) - get(id[j])));
	}
	chmin(res, get(id.back()) - get(id.front()));
}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	for (int i = 1;i <= n;++i)
		for (int j = 1;j <= m;++j)
			cin >> a[i][j];

	init();
	update();

	for (int l = 1, r = n;l < r;++l, --r)
		swap(a[l], a[r]);

	for (auto &[x, y] : id) 
		x = n - x + 1;

	update();

	for (int i = 1;i <= n;++i) {
		for (int l = 1, r = m;l < r;++l, --r)
			swap(a[i][l], a[i][r]);
	}
	for (auto &[x, y] : id) 
		y = m - y + 1;

	update();
	for (int l = 1, r = n;l < r;++l, --r)
		swap(a[l], a[r]);
	for (auto &[x, y] : id) 
		x = n - x + 1;
	update();

	cout << res << '\n';
}

Compilation message (stderr)

joioi.cpp: In function 'void update()':
joioi.cpp:48:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for (int i = 0, j = 0;i+1 < id.size();++i) {
      |                        ~~~~^~~~~~~~~~~

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