Submission #29519

#	Time	Username	Problem	Language	Result	Execution time	Memory
29519		cdemirer	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1319 ms	75852 KiB

joioi

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<pair<int, int> > vii;
typedef vector<vector<pair<int, int> > > vvii;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)

int H, W;
vector<pair<int, ii> > arr;
int ans = (int)1e9+7;
int fw1[2049], fw2[2049];

int fw1get(int pos) {
	pos += 1;
	int mxmm = -1;
	while (pos <= 2048) {
		mxmm = max(mxmm, fw1[pos]);
		pos += pos & -pos;
	}
	return mxmm;
}
int fw2get(int pos) {
	pos += 1;
	int mxmm = -1;
	while (pos <= 2048) {
		mxmm = max(mxmm, fw2[pos]);
		pos += pos & -pos;
	}
	return mxmm;
}
void fw1max(int pos, int val) {
	pos += 1;
	while (pos > 0) {
		fw1[pos] = max(fw1[pos], val);
		pos -= pos & -pos;
	}
}
void fw2max(int pos, int val) {
	pos += 1;
	while (pos > 0) {
		fw2[pos] = max(fw2[pos], val);
		pos -= pos & -pos;
	}
}

void calc() {
	for (int i = 0; i < 2049; i++) {
		fw1[i] = -1;
		fw2[i] = -1;
	}
	int i = 0, j = arr.size()-1;
	if (arr[j].second.first <= arr[i].second.first && arr[j].second.second <= arr[i].second.second) return;
	fw1max(arr[i].second.second, arr[i].second.first);
	fw2max(W-arr[j].second.second-1, H - arr[j].second.first - 1);
	int mini = arr[i].first, maxi = arr[j].first;
	int worst1 = 0, worst2 = 0;
	while (true) {
		worst1 = arr[j-1].first - mini;
		worst2 = maxi - arr[i+1].first;
		if (j == i+1) break;
		if (worst1 < worst2) {
			i++;
			ii pos = arr[i].second;
			int wall = fw2get(W-pos.second-1);
			if (pos.first >= H - wall - 1) break;
			fw1max(pos.second, pos.first);
		}
		else {
			j--;
			ii pos = arr[j].second;
			int wall = fw1get(pos.second);
			if (pos.first <= wall) break;
			fw2max(W-pos.second-1, H - pos.first - 1);
		}
	}
	//cerr << i << "," << j << " " << worst1 << " " << worst2 << endl;
	ans = min(ans, max(worst1, worst2));
}

void rotate() {
	for (int i = 0; i < arr.size(); i++) {
		arr[i].second = mp(arr[i].second.second, H-arr[i].second.first-1);
	}
	H = H ^ W;
	W = H ^ W;
	H = H ^ W;
}

void dump() {
	int mat[H][W];
	for (int i = 0; i < arr.size(); i++) {
		mat[arr[i].second.first][arr[i].second.second] = arr[i].first;
	}
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) { 
			cerr << mat[i][j] << " ";
		} cerr << endl;
	}
}

int main(int argc, char **argv) {

	//freopen("input", "r", stdin);
	//freopen("output", "w", stdout);

	scanf("%d%d", &H, &W);
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			int x; scanf("%d", &x);
			arr.pb(mp(x, mp(i, j)));
		}
	}
	sort(arr.begin(), arr.end());

	calc();
	rotate();
	//dump();
	calc();
	rotate();
	//dump();
	calc();
	rotate();
	//dump();
	calc();

	printf("%d\n", ans);

	return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'void rotate()':
joioi.cpp:85:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < arr.size(); i++) {
                    ^
joioi.cpp: In function 'void dump()':
joioi.cpp:95:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < arr.size(); i++) {
                    ^
joioi.cpp: In function 'int main(int, char**)':
joioi.cpp:110:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &H, &W);
                       ^
joioi.cpp:113:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int x; scanf("%d", &x);
                          ^

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