#include<bits/stdc++.h>
using namespace std;
//#define int long long
int n;int m;
int TPV;int BTV;
int gr[2010][2010];
int tgr[2010][2010];
int psmx[2010][2010];
int psmn[2010][2010];
int sfmx[2010][2010];
int sfmn[2010][2010];
int ans;
int chmx(int id,int l,int r){
if(l==1){
return psmx[id][r];
}
return sfmx[id][l];
}
int chmn(int id,int l,int r){
if(l==1){
return psmn[id][r];
}
return sfmn[id][l];
}
void spin(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
tgr[j][n-i+1 ]=gr[i][j];
}
}
swap(n,m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
gr[i][j]=tgr[i][j];
}
}
}
void precalc(){
for(int i=1;i<=n;i++){
psmn[i][1]=gr[i][1];
psmx[i][1]=gr[i][1];
for(int j=2;j<=m;j++){
psmn[i][j]=min(psmn[i][j-1],gr[i][j]);
psmx[i][j]=max(psmx[i][j-1],gr[i][j]);
}
sfmn[i][m]=gr[i][m];
sfmx[i][m]=gr[i][m];
for(int j=m-1;j>=1;j--){
sfmn[i][j]=min(sfmn[i][j+1],gr[i][j]);
sfmx[i][j]=max(sfmx[i][j+1],gr[i][j]);
}
}
}
int ok1(int mid){
int lst=m;
int tp=TPV-mid;
int bt=BTV+mid;
for(int i=1;i<=n;i++){
int l=0;int r=lst;
while(l<r){
int mi=l+(r-l+1)/2;
if((mi==0||(mi!=0&&chmn(i,1,mi)>=tp)) ){
l=mi;
}else{
r=mi-1;
}
}
lst=l;
if((lst!=m&&chmx(i,lst+1,m)>bt) ){return 0;}
}
return 1;
}
int ok2(int mid){
int lst=m;
int tp=TPV-mid;
int bt=BTV+mid;
for(int i=1;i<=n;i++){
int l=0;int r=lst;
while(l<r){
int mi=l+(r-l+1)/2;
if((mi==0||(mi!=0&&chmx(i,1,mi)<=bt)) ){
l=mi;
}else{
r=mi-1;
}
}
lst=l;
if((lst!=m&&chmn(i,lst+1,m)<tp) ){return 0;}
}
return 1;
}
int solve(){
int l=0;int r=1e9;
while(l<r){
int mi=l+(r-l)/2;
if((ok1(mi)||ok2(mi))){
r=mi;
}else{
l=mi+1;
}
}
return l;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>gr[i][j];
}
}
TPV=gr[1][1];BTV=gr[1][1];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
TPV=max(TPV,gr[i][j]);
BTV=min(BTV,gr[i][j]);
}
}
ans=1e9;
precalc();
ans=solve();
for(int t=1;t<=3;t++){
spin();
precalc();
ans=min(ans,solve());
}
cout<<ans<<endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
468 KB |
Output is correct |
2 |
Correct |
0 ms |
468 KB |
Output is correct |
3 |
Correct |
0 ms |
468 KB |
Output is correct |
4 |
Correct |
0 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
0 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
0 ms |
468 KB |
Output is correct |
12 |
Correct |
1 ms |
468 KB |
Output is correct |
13 |
Correct |
0 ms |
468 KB |
Output is correct |
14 |
Correct |
0 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
468 KB |
Output is correct |
2 |
Correct |
0 ms |
468 KB |
Output is correct |
3 |
Correct |
0 ms |
468 KB |
Output is correct |
4 |
Correct |
0 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
0 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
0 ms |
468 KB |
Output is correct |
12 |
Correct |
1 ms |
468 KB |
Output is correct |
13 |
Correct |
0 ms |
468 KB |
Output is correct |
14 |
Correct |
0 ms |
468 KB |
Output is correct |
15 |
Correct |
2 ms |
5204 KB |
Output is correct |
16 |
Correct |
8 ms |
5972 KB |
Output is correct |
17 |
Correct |
15 ms |
5972 KB |
Output is correct |
18 |
Correct |
15 ms |
6008 KB |
Output is correct |
19 |
Correct |
14 ms |
5972 KB |
Output is correct |
20 |
Correct |
13 ms |
5972 KB |
Output is correct |
21 |
Correct |
17 ms |
5972 KB |
Output is correct |
22 |
Correct |
18 ms |
5972 KB |
Output is correct |
23 |
Correct |
17 ms |
6072 KB |
Output is correct |
24 |
Correct |
16 ms |
6076 KB |
Output is correct |
25 |
Correct |
18 ms |
5972 KB |
Output is correct |
26 |
Correct |
17 ms |
5972 KB |
Output is correct |
27 |
Correct |
17 ms |
6052 KB |
Output is correct |
28 |
Correct |
17 ms |
5972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
468 KB |
Output is correct |
2 |
Correct |
0 ms |
468 KB |
Output is correct |
3 |
Correct |
0 ms |
468 KB |
Output is correct |
4 |
Correct |
0 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
0 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
0 ms |
468 KB |
Output is correct |
12 |
Correct |
1 ms |
468 KB |
Output is correct |
13 |
Correct |
0 ms |
468 KB |
Output is correct |
14 |
Correct |
0 ms |
468 KB |
Output is correct |
15 |
Correct |
2 ms |
5204 KB |
Output is correct |
16 |
Correct |
8 ms |
5972 KB |
Output is correct |
17 |
Correct |
15 ms |
5972 KB |
Output is correct |
18 |
Correct |
15 ms |
6008 KB |
Output is correct |
19 |
Correct |
14 ms |
5972 KB |
Output is correct |
20 |
Correct |
13 ms |
5972 KB |
Output is correct |
21 |
Correct |
17 ms |
5972 KB |
Output is correct |
22 |
Correct |
18 ms |
5972 KB |
Output is correct |
23 |
Correct |
17 ms |
6072 KB |
Output is correct |
24 |
Correct |
16 ms |
6076 KB |
Output is correct |
25 |
Correct |
18 ms |
5972 KB |
Output is correct |
26 |
Correct |
17 ms |
5972 KB |
Output is correct |
27 |
Correct |
17 ms |
6052 KB |
Output is correct |
28 |
Correct |
17 ms |
5972 KB |
Output is correct |
29 |
Correct |
1112 ms |
116768 KB |
Output is correct |
30 |
Correct |
1084 ms |
116236 KB |
Output is correct |
31 |
Correct |
1162 ms |
117960 KB |
Output is correct |
32 |
Correct |
1200 ms |
117772 KB |
Output is correct |
33 |
Correct |
1030 ms |
114188 KB |
Output is correct |
34 |
Correct |
1167 ms |
118020 KB |
Output is correct |
35 |
Correct |
1619 ms |
133480 KB |
Output is correct |
36 |
Correct |
1393 ms |
127988 KB |
Output is correct |
37 |
Correct |
1642 ms |
133584 KB |
Output is correct |