oj.uz

Submission #737732

# Submission time Handle Problem Language Result Execution time Memory
737732 2023-05-07T16:07:21 Z 1075508020060209tc The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 1 ms 468 KB 
#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 rmq[2010][12][2010];
int rmxq[2010][12][2010];
int ans;

int chmx(int id,int l,int r){
int lg=__lg(r-l+1);
return max(rmxq[id][lg][l],rmxq[id][lg][r-(1<<lg)+1]);
}
int chmn(int id,int l,int r){
int lg=__lg(r-l+1);
return min(rmq[id][lg][l],rmq[id][lg][r-(1<<lg)+1]);
}



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++){
    for(int j=1;j<=m;j++){
        rmq[i][0][j]=gr[i][j];
        rmxq[i][0][j]=gr[i][j];
    }
}
for(int t=1;t<=11;t++){
    for(int i=1;i<=n;i++){
        for(int j=1;j+(1<<t)-1<=m;j++){
            rmq[i][t][j]=min(rmq[i][t-1][j],rmq[i][t-1][j+(1<<(t-1))]);
            rmxq[i][t][j]=max(rmxq[i][t-1][j],rmxq[i][t-1][j+(1<<(t-1))]);
        }
    }
}
}

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<=0;t++){
    spin();
    precalc();
    ans=min(ans,solve());
}
cout<<ans<<endl;





}

Subtask #1
0 / 15.0

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

Subtask #2
0 / 45.0

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

Subtask #3
0 / 40.0

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