Submission #900235

#	Time	Username	Problem	Language	Result	Execution time	Memory
900235		Maite_Morale	The Kingdom of JOIOI (JOI17_joioi)	C++14	60 / 100	2689 ms	262144 KiB

joioi

#include<bits/stdc++.h>
#define F first
#define S second
#define MAX 2005
#define oo 1e18
#define mod 1000000007
#define fast_in ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(0);
using namespace std;
typedef long long ll;
#define pll pair<ll , ll>
#define vll vector<ll>
#define vvll vector<vll>
#define vpll vector<pll>
 
ll tmn[5][MAX][MAX],tmx[5][MAX][MAX],n,a[MAX][MAX],m;
vll v;
map<ll,ll> mp;
ll OK(ll y,ll z){
    if(y+1==v.size())return abs(v[0]-v.back());
    ll x=v[y];
    //cout<<x<<":";
    ll cl=-1,mx=0,mn=oo;
    for(int i=0;i<n;i++){
        while(cl!=m && tmn[0][i][cl+1]<=x)cl++;
        if(cl!=-1)mx=max(mx,tmx[1][i][cl]);
    }//cout<<mx<<" ";
    mn=min(mn,mx);
    cl=m,mx=0;
    for(int i=0;i<n;i++){
        while(cl-1>=0 && tmn[1][i][cl-1]<=x)cl--;
        if(cl!=-1)mx=max(mx,tmx[0][i][cl]);
    }//cout<<mx<<" ";
    mn=min(mn,mx);
    cl=-1,mx=0;
    for(int i=n-1;i>=0;i--){
        while(cl!=m && tmn[0][i][cl+1]<=x)cl++;
        if(cl!=-1)mx=max(mx,tmx[1][i][cl]);
    }//cout<<mx<<" ";
    mn=min(mn,mx);
    cl=m,mx=0;
    for(int i=n-1;i>=0;i--){
        while(cl-1>=0 && tmn[1][i][cl-1]<=x)cl--;
        if(cl!=-1)mx=max(mx,tmx[0][i][cl]);
    }
    mn=min(mn,mx);
    if(z==1)return max(abs(v[0]-mn),abs(v.back()-v[y+1]));
    if(abs(v[0]-mn)<abs(v.back()-v[y+1]))return 1;
return 0; 
}
int main(){
    fast_in
    cin>>n>>m;
    for(int i=0;i<n;i++){
        tmn[0][i][m]=tmn[1][i][0]=oo;
        for(int j=0;j<m;j++){
            cin>>a[i][j];
            if(mp[a[i][j]]==0){
                mp[a[i][j]]=1;
                v.push_back(a[i][j]);
            }
            tmx[1][i][j]=max(tmx[1][i][j],a[i][j]);
            tmx[1][i][j+1]=tmx[1][i][j];
            tmn[1][i][j]=min(tmn[1][i][j],a[i][j]);
            tmn[1][i][j+1]=tmn[1][i][j];
        }
        for(int j=m-1;j>=0;j--){
            tmx[0][i][j]=max(tmx[0][i][j+1],a[i][j]);
            tmn[0][i][j]=min(tmn[0][i][j+1],a[i][j]);
        }
    }
    sort(v.begin(),v.end());
    // for(auto i:v)cout<<i<<" ";cout<<"\n";
    ll p=0,f=v.size();
    while(abs(f-p)!=1){
        ll md=(p+f)/2;                     // cout<<md;
        if(OK(md,0)==1)p=md;
        else             f=md;           
    }                                          
    if(f==v.size()){cout<<0;return 0;}
    //  cout<<p<<" "<<f<<" ";
    cout<<min(OK(p,1),OK(f,1));
return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'll OK(ll, ll)':
joioi.cpp:19:11: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     if(y+1==v.size())return abs(v[0]-v.back());
      |        ~~~^~~~~~~~~~
joioi.cpp: In function 'int main()':
joioi.cpp:79:9: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     if(f==v.size()){cout<<0;return 0;}
      |        ~^~~~~~~~~~

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