#pragma gcc optimize ("Ofast")
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <bitset>
#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;
vector<short> cnt;
vector<vector<int>> 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_unlocked(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 int y, const int 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();
pos.resize(sz + 5);
cnt.resize(sz + 5);
for(int i = 0; i < N; i++) for(int j = 0; j < M; j++){
arr[i][j] = lower_bound(lisan.begin(), lisan.begin() + sz, arr[i][j]) - lisan.begin();
cnt[arr[i][j]]++;
pos[arr[i][j]].emplace_back(i * M + 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 += 2){
//take all of them
//
//cout << "i = " << i << ", = " << lisan[i] << endl;
for(int id : pos[i]){
take(id / M, id - id / M * M, mx, mn, jizz);
}
if(lisan[mx] - lisan[mn] > ans) break;
/*
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[f]) f++;
while(e && !cnt[e]) e--;
if(f == sz || !e) break;
ans = min(ans, max(lisan[e] - lisan[f], lisan[mx] - lisan[mn]));
//cout << "ans = " << ans << endl;
}
rot();
}
cout << ans << '\n';
}
Compilation message
joioi.cpp:1: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
1 | #pragma gcc optimize ("Ofast")
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
0 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
0 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
0 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
