oj.uz

Submission #370337

# Submission time Handle Problem Language Result Execution time Memory
370337 2021-02-23T19:52:34 Z shivensinha4 The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 1 ms 364 KB 
#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
#define endl '\n'

int n, m;
vector<vi> mat;
const int INF = 1e9;
int fin;
vi nums;

void solve() {
	int l = 0, r = (int) nums.size()-1, ans = r;
	vi wd(n);
	while (l < r) {
		int mid = (l+r)/2;
		bool valid = true;
		for_(i, 0, n) {
			int pt = -1;
			for_(j, 0, m) {
				if (mat[i][j] > nums[mid]) break;
				pt = j;
			}
			if (i > 0) pt = min(pt, wd[i-1]);
			wd[i] = pt;
		}
		
		int mn = INF;
		if (valid) for_(i, 0, n) for_(j, wd[i]+1, m) {
			mn = min(mn, mat[i][j]);
		}
		if (nums.back()-mn > nums[mid]-nums[0]) valid = false;
		if (!valid) l = mid+1;
		else {
			r = ans = mid;
		}
	}
	
	fin = min(fin, nums[ans]-nums[0]);
}

void rotate() {
	vector<vi> temp(m, vi(n));
	for (int j = m-1; j >= 0; j--) {
		for_(i, 0, n) temp[m-j-1][i] = mat[i][j];
	}
	swap(n, m);
	swap(mat, temp);
}

void rotateAndSolve() {
	solve();
	for_(i, 0, n) reverse(mat[i].begin(), mat[i].end());
	solve();
}


int main() {
#ifdef mlocal
	freopen("test.in", "r", stdin);
#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
	mat.resize(n, vi(m)); nums.reserve(n*m);
	for_(i, 0, n) for_(j, 0, m) {
		cin >> mat[i][j];
		nums.push_back(mat[i][j]);
	}
	
	sort(nums.begin(), nums.end());
	fin = nums.back()-nums[0];
	rotateAndSolve();
	for_(i, 0, n) for_(j, 0, m) mat[i][j] = -mat[i][j];
	reverse(nums.begin(), nums.end());
	for_(i, 0, nums.size()) nums[i] = -nums[i];
	rotateAndSolve();
	
	cout << fin << endl;
	
	
	return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -