Submission #670459

#	Time	Username	Problem	Language	Result	Execution time	Memory
670459		Mahdi	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	1075 ms	43816 KiB

joioi

#include<bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
const int N=2005;
int n, m, a[N][N], rens;
vector<int>v;

int num(bool x, bool y, int h){
    int mx=1, mn=1e9;
    if(x){
        int r=(y ? m : -1);
        for(int i=0;i<n;++i){
            if(y){
                int j=0;
                for(;j<r;++j){
                    if(a[i][j]>h)
                        break;
                }
                r=j;
                for(j=r;j<m;++j){
                    mn=min(mn, a[i][j]);
                    mx=max(mx, a[i][j]);
                }
            }
            else{
                int j=m-1;
                for(;j>r;--j){
                    if(a[i][j]>h)
                        break;
                }
                r=j;
                for(j=r;j>=0;--j){
                    mn=min(mn, a[i][j]);
                    mx=max(mx, a[i][j]);
                }
            }
        }
    }
    else{
        int r=(y ? m : -1);
        for(int i=n-1;i>=0;--i){
            if(y){
                int j=0;
                for(;j<r;++j){
                    if(a[i][j]>h)
                        break;
                }
                r=j;
                for(j=r;j<m;++j){
                    mn=min(mn, a[i][j]);
                    mx=max(mx, a[i][j]);
                }
            }
            else{
                int j=m-1;
                for(;j>r;--j){
                    if(a[i][j]>h)
                        break;
                }
                r=j;
                for(j=r;j>=0;--j){
                    mn=min(mn, a[i][j]);
                    mx=max(mx, a[i][j]);
                }
            }
        }
    }
    return mx-mn;
}

void ans(bool x, bool y){
    int l=-1, r=v.size();
    while(r>l+1){
        int md=(l+r)/2;
        int mm=num(x, y, v[md]);
        if(mm<v[md]-v[0])
            r=md;
        else
            l=md;
    }
    if(r<v.size())
        rens=min(rens, v[r]-v[0]);
    if(l>=0)
        rens=min(rens, num(x, y, v[l]));
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            cin>>a[i][j];
            v.push_back(a[i][j]);
        }
    }
    sort(all(v));
    v.resize(distance(v.begin(), unique(all(v))));
    rens=2e9;
    ans(0, 0);
    ans(0, 1);
    ans(1, 0);
    ans(1, 1);
    cout<<rens<<'\n';   
}

Compilation message (stderr)

joioi.cpp: In function 'void ans(bool, bool)':
joioi.cpp:85:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     if(r<v.size())
      |        ~^~~~~~~~~

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