제출 #737733

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
737733		1075508020060209tc	The Kingdom of JOIOI (JOI17_joioi)	C++14	60 / 100	1205 ms	262144 KiB

joioi

#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][13][2010];
int rmxq[2010][13][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<=12;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<=3;t++){
    spin();
    precalc();
    ans=min(ans,solve());
}
cout<<ans<<endl;





}

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