Submission #322461

#	Time	Username	Problem	Language	Result	Execution time	Memory
322461		Seanliu	The Kingdom of JOIOI (JOI17_joioi)	C++17	60 / 100	4050 ms	72216 KiB

joioi

#pragma gcc optimize ("O3")
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <bitset>
#include <unordered_map>
#define ericxiao ios_base::sync_with_stdio(0);cin.tie(0);
#define pii pair<int,int>
#define F first
#define S second
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;

const int maxN = 2e3 + 326, INF = 2e9 + 326;

int N, M, arr[maxN][maxN], sz, ii, jj;
vector<int> lisan;
unordered_map<int, short> cnt;
unordered_map<int, vector<pair<short,short>>> pos;
bitset<maxN> vis[maxN];

inline char readchar() {
    static const size_t bufsize = 65536;
    static char buf[bufsize];
    static char *p = buf, *end = buf;
    if (p == end) end = buf + fread(buf, 1, bufsize, stdin), p = buf;
    return *p++;
}

inline void const Read(int & p) {
	p = 0;
	int tmp = 0;
	char c = readchar();
	tmp = !(c^'-');
	while (c < '0' || c > '9') {
		c = readchar();
	}
	while (c >= '0' && c <= '9')
		p = (p<<3)+(p<<1)+(c^48), c = readchar();
	p = tmp?-p:p;
}

inline void take(const short &y, const short &x, int &mx, int &mn, int &d){
	if(d == 0){
		for(ii = y; ii >= 0 && !vis[ii][x]; ii--){
			for(jj= x; jj >= 0 && !vis[ii][jj]; jj--){
				vis[ii][jj] = true;
				cnt[arr[ii][jj]]--;
				mx = max(mx, arr[ii][jj]);
				mn = min(mn, arr[ii][jj]);
			}
		}
	} else if(d == 1){
		for(ii = y; ii < N && !vis[ii][x]; ii++){
			for(jj= x; jj >= 0 && !vis[ii][jj]; jj--){
				vis[ii][jj] = true;
				cnt[arr[ii][jj]]--;
				mx = max(mx, arr[ii][jj]);
				mn = min(mn, arr[ii][jj]);
			}
		}
	} else if(d == 2){
		for(ii = y; ii < N && !vis[ii][x]; ii++){
			for(jj= x; jj < M && !vis[ii][jj]; jj++){
				vis[ii][jj] = true;
				cnt[arr[ii][jj]]--;
				mx = max(mx, arr[ii][jj]);
				mn = min(mn, arr[ii][jj]);
			}
		}
	} else if(d == 3){
		for(ii = y; ii >= 0 && !vis[ii][x]; ii--){
			for(jj= x; jj < M && !vis[ii][jj]; jj++){
				vis[ii][jj] = true;
				cnt[arr[ii][jj]]--;
				mx = max(mx, arr[ii][jj]);
				mn = min(mn, arr[ii][jj]);
			}
		}
	}
}

inline void rot(){
	for(ii = 0; ii < sz; ii++){
		cnt[ii] = 0;
	}
	for(ii = 0; ii < N; ii++) for(jj = 0; jj < M; jj++) {
		vis[ii].reset();
		cnt[arr[ii][jj]]++;
	}
}

int main(){
	Read(N);
	Read(M);
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			Read(arr[i][j]);
			lisan.push_back(arr[i][j]);
		}
	}
	sort(lisan.begin(), lisan.end());
	sz = unique(lisan.begin(), lisan.end()) - lisan.begin();
	cnt.reserve(sz);
	pos.reserve(sz);
	for(int i = 0; i < N; i++) for(int j = 0; j < M; j++){
		cnt[arr[i][j]]++;
		if(!pos.count(arr[i][j])){
			pos[arr[i][j]] = vector<pair<short,short>>();
			//cout << "hello" << arr[i][j] << endl;
		}
		pos[arr[i][j]].emplace_back(i, j);
	}
	int ans = lisan[sz - 1] - lisan[0];
	for(int jizz = 0; jizz < 4; jizz++){
		//cout << "in jizz = " << jizz << endl;
		int mx = -INF, mn = INF, f = 0, e = sz - 1;
		for(int i = 0; i < sz; i++){
			//take all of them
			//
			//cout << "i = " << i << ", = " << lisan[i] << endl;
			for(auto &[y, x] : pos[lisan[i]]){
				take(y, x, mx, mn, jizz);
			}
			/*
			for(int y = 0; y < N; y++) for(int x = 0; x < M; x++){
				cout << vis[y][x] << " \n"[x == M - 1];
			}
			*/
			while(f < sz - 1 && !cnt[lisan[f]]) f++;
			while(e && !cnt[lisan[e]]) e--;
			if(f == sz || !e) break;
			ans = min(ans, max(lisan[e] - lisan[f], mx - mn));
			//cout << "ans = " << ans << endl;
		}
		rot();
	}
	cout << ans << '\n';
}

Compilation message (stderr)

joioi.cpp:1: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    1 | #pragma gcc optimize ("O3")
      |

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