Submission #68262

#	Time	Username	Problem	Language	Result	Execution time	Memory
68262		Nurlykhan	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	1327 ms	121296 KiB

joioi

#include <bits/stdc++.h>

#define pb push_back
#define all(v) v.begin(), v.end()
#define sz(v) int(v.size())
#define pii pair<int, int>
#define mp make_pair
#define f first
#define ll long long
#define ld long double
#define s second
#define vec vector<int>

using namespace std;

const int N = (int) 2e3 + 100;
const int M = (int) 2018 * 2018;
const int K = (int) 10;
const int INF = (int) 1e9 + 7;
const int mod = (int) 998244353;
const ld EPS = (ld) 1e-9;
const ll LINF = (ll) 1e18;

int n, m;
vector<vector<int> > a;
int mx;
int pref[N][N], suff_max[N][N], suff_min[N][N];

void precalc() {
	// global max
	int cur_n = sz(a);
	int cur_m = sz(a[0]);
	mx = 0;
	for (int i = 0; i < cur_n; i++) {
		for (int j = 0; j < cur_m; j++) {
			mx = max(mx, a[i][j]);
		}
	}
	for (int i = 0; i < cur_n; i++) {
		for (int j = 0; j < cur_m; j++) {
			pref[i][j] = a[i][j];
			if (j > 0) 
				pref[i][j] = min(pref[i][j], pref[i][j - 1]);
		}
		suff_min[i][cur_m] = INF;
		suff_max[i][cur_m] = 0;
		for (int j = cur_m - 1; j >= 0; j--) {
			suff_max[i][j] = max(a[i][j], suff_max[i][j + 1]);
			suff_min[i][j] = min(a[i][j], suff_min[i][j + 1]);
		}
	}
}

bool ok(int diff) {
	int cur_n = sz(a);
	int cur_m = sz(a[0]);
	int ptr = cur_m - 1;
	int max_val = mx;
	int mn = INF, mx = 0;
	for (int i = 0; i < cur_n; i++) {
		while (ptr >= 0 && max_val > diff + pref[i][ptr]) {
			ptr--;
		}
		mn = min(mn, suff_min[i][ptr + 1]);
		mx = max(mx, suff_max[i][ptr + 1]);
	}
	return mx - mn <= diff;
}

void mirror() {
	for (int i = 0; i < n / 2; i++) {
		for (int j = 0; j < m; j++) {
			swap(a[i][j], a[n - 1 - i][j]);
		}
	}
}

void rotate() {
	int b[N][N];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			b[j][n - i - 1] = a[i][j];
		}
	}
	swap(n, m);
	a.clear();
	for (int i = 0; i < n; i++) {
		a.pb(vector<int>(m));
		for (int j = 0; j < m; j++) {
			a[i][j] = b[i][j];
		}
	}
}

int main() {
	#ifdef sony
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif
	srand(time(0));
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		a.pb(vector<int>(m));
		for (int j = 0; j < m; j++) {
			scanf("%d", &a[i][j]);
		}
	}
	int ans = INF;
	for (int i = 0; i < 4; i++) {
		precalc();
		int l = 1, r = ans - 1;
		while (l <= r) {
			int mid = (l + r) / 2;
			if (ok(mid)) {
				r = mid - 1;
				ans = mid;
			} else {
				l = mid + 1;
			}
		}
		mirror();
		precalc();
	    l = 1, r = ans - 1;
		while (l <= r) {
			int mid = (l + r) / 2;
			if (ok(mid)) {
				r = mid - 1;
				ans = mid;
			} else {
				l = mid + 1;
			}
		}
		mirror();
		rotate();
	}
	cout << ans;
	return 0;	
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:105:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~

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