Submission #68285

#	Time	Username	Problem	Language	Result	Execution time	Memory
68285		BThero	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	3509 ms	114748 KiB

joioi

// Why I am so dumb? :c
#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;

typedef long long ll;

const int MAXN = (int)2e3 + 3;
const int INF = (int)2e9;

pair<int, int> pref[MAXN][MAXN];

pair<int, int> suff[MAXN][MAXN];

int newArr[MAXN][MAXN];

int arr[MAXN][MAXN];

int rl[MAXN * MAXN];

int n, m, k, ans;

void compress() {
	vector<int> vv;

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			vv.pb(arr[i][j]);
		}
	}

	sort(all(vv));
	vv.resize(unique(all(vv)) - vv.begin());

	k = vv.size();

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			int ps = upper_bound(all(vv), arr[i][j]) - vv.begin();
			rl[ps] = arr[i][j];
			arr[i][j] = ps;
		}
	}
}

int goPrefL(int lim) {
	int ptr = m, cur = 0, cur2 = 0;

    for (int i = 1; i <= n; ++i) {
    	while (ptr > 0 && pref[i][ptr].se < lim) {
    		--ptr;
    	}

    	if (ptr < 1) {
	   		break;
	   	}

    	cur = max(cur, pref[i][ptr].fi);

    	if (ptr < m) {
    		cur2 = max(cur2, suff[i][ptr + 1].fi);
    	}
    }

    if (ptr > 0 && cur == k) {
    	return max(rl[k] - rl[lim], rl[cur2] - rl[1]);
    }	
    
    return INF;
}

int goSuffL(int lim) {
	int ptr = 1, cur = 0, cur2 = 0;

    for (int i = 1; i <= n; ++i) {
    	while (ptr <= m && suff[i][ptr].se < lim) {
    		++ptr;
    	}

    	if (ptr > m) {
    		break;
    	}

    	cur = max(cur, suff[i][ptr].fi);

    	if (ptr > 1) {
    		cur2 = max(cur2, pref[i][ptr - 1].fi);
    	}
    }

    if (ptr <= m && cur == k) {
    	return max(rl[k] - rl[lim], rl[cur2] - rl[1]);
    }	
    
    return INF;
}

int goPrefR(int lim) {
	int ptr = m, cur = k + 1, cur2 = k + 1;
			
    for (int i = 1; i <= n; ++i) {
    	while (ptr > 0 && pref[i][ptr].fi > lim) {
    		--ptr;
    	}

    	if (ptr < 1) {
    		break;
    	}

    	cur = min(cur, pref[i][ptr].se);

    	if (ptr < m) {
    		cur2 = min(cur2, suff[i][ptr + 1].se);
    	}
    }

    if (ptr > 0 && cur == 1) {
    	return max(rl[lim] - rl[1], rl[k] - rl[cur2]);
	}

	return INF;
}

int goSuffR(int lim) {
    int ptr = 1, cur = k + 1, cur2 = k + 1;

    for (int i = 1; i <= n; ++i) {
    	while (ptr <= m && suff[i][ptr].fi > lim) {
    		++ptr;
    	}

    	if (ptr > m) {
    		break;
    	}

    	cur = min(cur, suff[i][ptr].se);

    	if (ptr > 1) {
    		cur2 = min(cur2, pref[i][ptr - 1].se);
    	}
    }

    if (ptr <= m && cur == 1) {
    	return max(rl[lim] - rl[1], rl[k] - rl[cur2]);
    }	

    return INF;
}

void solve() {                   
	scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; ++i) {
    	for (int j = 1; j <= m; ++j) {
    		scanf("%d", &arr[i][j]);
    	}
    }

    compress();
    // fi -> max, se -> min

    ans = rl[k] - rl[1];

    for (int step = 0; step < 4; ++step) {    	
    	for (int i = 1; i <= n; ++i) {
    		pref[i][1] = mp(arr[i][1], arr[i][1]);
    		suff[i][m] = mp(arr[i][m], arr[i][m]);

    		for (int j = 2; j <= m; ++j) {              
    			pref[i][j].fi = max(pref[i][j - 1].fi, arr[i][j]);
    			pref[i][j].se = min(pref[i][j - 1].se, arr[i][j]);
    		}

    		for (int j = m - 1; j > 0; --j) {
    			suff[i][j].fi = max(suff[i][j + 1].fi, arr[i][j]);
    			suff[i][j].se = min(suff[i][j + 1].se, arr[i][j]);
    		}
    	}    	

    	{
    		int l = 2, r = k;

    		while (r - l > 5) {
    			int m1 = l + (r - l) / 3;
    			int m2 = r - (r - l) / 3;

    			if (goPrefL(m1) > goPrefL(m2)) {
    				l = m1;
    			}
    			else {
    				r = m2;
    			}
    		}

    		for (int i = l; i <= r; ++i) {
    			ans = min(ans, goPrefL(i));	
    		}
    	}

    	{
    		int l = 2, r = k;

    		while (r - l > 5) {
    			int m1 = l + (r - l) / 3;
    			int m2 = r - (r - l) / 3;

    			if (goSuffL(m1) > goSuffL(m2)) {
    				l = m1;
    			}
    			else {
    				r = m2;
    			}
    		}

    		for (int i = l; i <= r; ++i) {
    			ans = min(ans, goSuffL(i));	
    		}
    	}

    	{
    		int l = 1, r = k - 1;

    		while (r - l > 5) {
    			int m1 = l + (r - l) / 3;
    			int m2 = r - (r - l) / 3;

    			if (goPrefR(m1) > goPrefR(m2)) {
    				l = m1;
    			}
    			else {
    				r = m2;
    			}
    		}

    		for (int i = l; i <= r; ++i) {
    			ans = min(ans, goPrefR(i));	
    		}
    	}

    	{
    		int l = 1, r = k - 1;

    		while (r - l > 5) {
    			int m1 = l + (r - l) / 3;
    			int m2 = r - (r - l) / 3;

    			if (goSuffR(m1) > goSuffR(m2)) {
    				l = m1;
    			}
    			else {
    				r = m2;
    			}
    		}

    		for (int i = l; i <= r; ++i) {
    			ans = min(ans, goSuffR(i));	
    		}
    	}
		
		// rotate array

		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= m; ++j) {
				newArr[m - j + 1][i] = arr[i][j];
			}
		}

		swap(n, m);

		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= m; ++j) {
				arr[i][j] = newArr[i][j];
			}
		}
    }

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

int main() {    
    int tt = 1;

    while (tt--) {
        solve();
    }

    return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'void solve()':
joioi.cpp:159:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
joioi.cpp:163:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &arr[i][j]);
       ~~~~~^~~~~~~~~~~~~~~~~~

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