제출 #1173728

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1173728		AlgorithmWarrior	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	1397 ms	47616 KiB

joioi

#include <bits/stdc++.h>

using namespace std;

int const MAX=4e6+5;
struct block{
    int l,c,val;
    bool operator<(block ot){
        return val<ot.val;
    }
}blocks[MAX];
int n,m;
int minim[MAX],maxim[MAX];

void read(){
    cin>>n>>m;
    int i,j;
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j){
            int val;
            cin>>val;
            blocks[(i-1)*m+j]={i,j,val};
        }
    sort(blocks+1,blocks+n*m+1);
}

void minself(int& x,int val){
    if(x>val)
        x=val;
}

void maxself(int& x,int val){
    if(x<val)
        x=val;
}

bool check_matrix(int l1,int r1,int l2,int r2){
    int i;
    for(i=1;i<=n;++i){
        minim[i]=m+1;
        maxim[i]=0;
    }
    for(i=l1;i<=r1;++i){
        auto [l,c,val]=blocks[i];
        maxself(maxim[l],c);
    }
    for(i=l2;i<=r2;++i){
        auto [l,c,val]=blocks[i];
        minself(minim[l],c);
    }
    for(i=1;i<=n;++i)
        if(maxim[i]>minim[i])
            return 0;
    int mxm=0;
    for(i=1;i<=n;++i){
        maxself(mxm,maxim[i]);
        if(mxm>=minim[i])
            break;
    }
    if(i==n+1)
        return 1;
    mxm=0;
    for(i=n;i;--i){
        maxself(mxm,maxim[i]);
        if(mxm>=minim[i])
            break;
    }
    if(i==0)
        return 1;
    return 0;
}

bool check(int val){
    int i;
    for(i=1;i<=n*m;++i)
        if(blocks[i].val-blocks[1].val>val && blocks[n*m].val-blocks[i].val>val)
            return 0;
    int st=1,dr=n*m;
    /// (]
    while(dr-st>1){
        int mij=(st+dr)/2;
        if(blocks[mij].val-blocks[1].val>val)
            dr=mij;
        else
            st=mij;
    }
    int id2=dr;
    st=1,dr=n*m;
    /// [)
    while(dr-st>1){
        int mij=(st+dr)/2;
        if(blocks[n*m].val-blocks[mij].val>val)
            st=mij;
        else
            dr=mij;
    }
    int id1=st;
    if(check_matrix(1,id1,id2,n*m))
        return 1;
    if(check_matrix(id2,n*m,1,id1))
        return 1;
    return 0;
}

int bin_search(){
    /// (]
    int st=-1,dr=blocks[n*m].val-blocks[1].val;
    while(dr-st>1){
        int mij=(st+dr)/2;
        if(check(mij))
            dr=mij;
        else
            st=mij;
    }
    return dr;
}

int main()
{
    read();
    cout<<bin_search();
    return 0;
}

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