oj.uz

Submission #68285

# Submission time Handle Problem Language Result Execution time Memory
68285 2018-08-16T11:16:41 Z BThero The Kingdom of JOIOI (JOI17_joioi) C++17
100 / 100
 3509 ms 114748 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)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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 628 KB Output is correct
3 Correct 4 ms 676 KB Output is correct
4 Correct 2 ms 676 KB Output is correct
5 Correct 3 ms 676 KB Output is correct
6 Correct 3 ms 676 KB Output is correct
7 Correct 3 ms 676 KB Output is correct
8 Correct 3 ms 708 KB Output is correct
9 Correct 2 ms 708 KB Output is correct
10 Correct 4 ms 836 KB Output is correct
11 Correct 2 ms 836 KB Output is correct
12 Correct 3 ms 836 KB Output is correct
13 Correct 2 ms 836 KB Output is correct
14 Correct 3 ms 836 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 628 KB Output is correct
3 Correct 4 ms 676 KB Output is correct
4 Correct 2 ms 676 KB Output is correct
5 Correct 3 ms 676 KB Output is correct
6 Correct 3 ms 676 KB Output is correct
7 Correct 3 ms 676 KB Output is correct
8 Correct 3 ms 708 KB Output is correct
9 Correct 2 ms 708 KB Output is correct
10 Correct 4 ms 836 KB Output is correct
11 Correct 2 ms 836 KB Output is correct
12 Correct 3 ms 836 KB Output is correct
13 Correct 2 ms 836 KB Output is correct
14 Correct 3 ms 836 KB Output is correct
15 Correct 7 ms 3912 KB Output is correct
16 Correct 15 ms 4900 KB Output is correct
17 Correct 22 ms 5028 KB Output is correct
18 Correct 24 ms 5028 KB Output is correct
19 Correct 23 ms 5164 KB Output is correct
20 Correct 22 ms 5220 KB Output is correct
21 Correct 26 ms 5220 KB Output is correct
22 Correct 24 ms 5220 KB Output is correct
23 Correct 23 ms 5220 KB Output is correct
24 Correct 20 ms 5220 KB Output is correct
25 Correct 24 ms 5220 KB Output is correct
26 Correct 22 ms 5220 KB Output is correct
27 Correct 23 ms 5220 KB Output is correct
28 Correct 25 ms 5220 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 628 KB Output is correct
3 Correct 4 ms 676 KB Output is correct
4 Correct 2 ms 676 KB Output is correct
5 Correct 3 ms 676 KB Output is correct
6 Correct 3 ms 676 KB Output is correct
7 Correct 3 ms 676 KB Output is correct
8 Correct 3 ms 708 KB Output is correct
9 Correct 2 ms 708 KB Output is correct
10 Correct 4 ms 836 KB Output is correct
11 Correct 2 ms 836 KB Output is correct
12 Correct 3 ms 836 KB Output is correct
13 Correct 2 ms 836 KB Output is correct
14 Correct 3 ms 836 KB Output is correct
15 Correct 7 ms 3912 KB Output is correct
16 Correct 15 ms 4900 KB Output is correct
17 Correct 22 ms 5028 KB Output is correct
18 Correct 24 ms 5028 KB Output is correct
19 Correct 23 ms 5164 KB Output is correct
20 Correct 22 ms 5220 KB Output is correct
21 Correct 26 ms 5220 KB Output is correct
22 Correct 24 ms 5220 KB Output is correct
23 Correct 23 ms 5220 KB Output is correct
24 Correct 20 ms 5220 KB Output is correct
25 Correct 24 ms 5220 KB Output is correct
26 Correct 22 ms 5220 KB Output is correct
27 Correct 23 ms 5220 KB Output is correct
28 Correct 25 ms 5220 KB Output is correct
29 Correct 1868 ms 95460 KB Output is correct
30 Correct 1915 ms 98496 KB Output is correct
31 Correct 2085 ms 98508 KB Output is correct
32 Correct 1905 ms 98636 KB Output is correct
33 Correct 1578 ms 98636 KB Output is correct
34 Correct 1930 ms 98636 KB Output is correct
35 Correct 3509 ms 113700 KB Output is correct
36 Correct 2585 ms 113700 KB Output is correct
37 Correct 3148 ms 114748 KB Output is correct