Submission #647579

#	Time	Username	Problem	Language	Result	Execution time	Memory
647579		ymm	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	2947 ms	128472 KiB

joioi

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 2048;
int a[N][N];
int n, m;

int len[N];

bool can_extend(int i, int mx)
{
	if (i > 0 && len[i-1] <= len[i])
		return 0;
	if (len[i] == m || a[i][len[i]] > mx)
		return 0;
	return 1;
}

int solve()
{
	static bool col[N][N];
	int mn1v = 2e9, mx1v = -1, mn2 = 0, mx2 = n*m-1;
	vector<pair<int,pii>> alts;
	memset(len, 0, sizeof(len));
	Loop (i,0,n) Loop (j,0,m) {
		alts.push_back({a[i][j], {i, j}});
		col[i][j] = 1;
	}
	sort(alts.begin(), alts.end());
	int ans = 2e9;
	for (auto [mx, pos] : alts) {
		int row = pos.first;
		Loop (r,row,n) {
			if (!can_extend(r, mx))
				break;
			while (can_extend(r, mx)) {
				mx1v = max(mx1v, a[r][len[r]]);
				mn1v = min(mn1v, a[r][len[r]]);
				col[r][len[r]] = 0;
				len[r]++;
			}
		}
		for (; mn2 <  n*m && !col[alts[mn2].second.first][alts[mn2].second.second]; ++mn2);
		for (; mx2 >= 0   && !col[alts[mx2].second.first][alts[mx2].second.second]; --mx2);
		if (mx1v == -1 || mx2 == -1)
			continue;
		ans = min(ans, max(mx1v - mn1v, alts[mx2].first - alts[mn2].first));
	}
	return ans;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m;
	Loop (i,0,n) Loop (j,0,m)
		cin >> a[i][j];
	int ans = 2e9;
	ans = min(ans, solve());
	Loop (i,0,n/2) Loop (j,0,m)
		swap(a[i][j], a[n-1-i][j]);
	ans = min(ans, solve());
	Loop (i,0,n) Loop (j,0,m/2)
		swap(a[i][j], a[i][m-1-j]);
	ans = min(ans, solve());
	Loop (i,0,n/2) Loop (j,0,m)
		swap(a[i][j], a[n-1-i][j]);
	ans = min(ans, solve());
	cout << ans << '\n';
}

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