oj.uz

Submission #68249

# Submission time Handle Problem Language Result Execution time Memory
68249 2018-08-16T09:57:04 Z BThero The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 2 ms 376 KB 
// 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)2e2 + 3;

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;
		}
	}
}

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]);
    		}
    	}

    	// L first

    	for (int lim = 2; lim <= k; ++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) {
    			ans = min(ans, max(rl[k] - rl[lim], rl[cur2] - rl[1]));
    		}
    		}

    		{
    		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 > 0 && cur == k) {
    			ans = min(ans, max(rl[k] - rl[lim], rl[cur2] - rl[1]));
    		}
    		}
    	}

    	// for R
    	for (int lim = 1; lim < k; ++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) {
    			ans = min(ans, max(rl[lim] - rl[1], rl[k] - rl[cur2]));
    		}
    		}

    		{
    		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 > 0 && cur == 1) {
    			ans = min(ans, max(rl[lim] - rl[1], rl[k] - rl[cur2]));
    		}
    		}
    	}
		
		// 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

joioi.cpp: In function 'void solve()':
joioi.cpp:54: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:58: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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -