Submission #258308

#	Time	Username	Problem	Language	Result	Execution time	Memory
258308		uacoder123	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	2968 ms	197956 KiB

joioi

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))

typedef int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
typedef tree<pair<lli,int>,null_type,less<pair<lli,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
int n,m,ma=0,mi=1000000000;
int arr[2001][2001];
ii l1[2001][2001],s1[2001][2001];
vector<pair<int,pair<ii,ii>>> v1[2001];
int check(int v,int t,int v3)
{
  int ma1=mi,i,mi1=ma;
  if(t<2)
    i=0;
  else
    i=n+1;
  for(int j=1;j<=m;++j)
  {
    auto it=lower_bound(all(v1[j]),mp(v,mp(mp(-1,-1),mp(-1,-1))))-v1[j].begin();
    it--;
    auto it1=lower_bound(all(v1[j]),mp(v+1,mp(mp(-1,-1),mp(-1,-1))))-v1[j].begin();
    int l;
    if(t==0)
    {
      if(it==-1)
        l=0;
      else
        l=v1[j][it].S.F.F;
      i=max(l,i);
      if(i!=0&&i!=n+1)
        ma1=max(ma1,l1[j][i].F);
    }
    else if(t==3)
    {
      if(it==-1)
        l=n+1;
      else
        l=v1[j][it].S.F.S;
      i=min(l,i);
      if(i!=0&&i!=n+1)
      ma1=max(ma1,l1[j][i].S);
    }
    else if(t==1)
    {
      if(it1==n)
        l=0;
      else
        l=v1[j][it1].S.S.F;
      i=max(l,i);
      if(i!=0&&i!=n+1)
      mi1=min(mi1,s1[j][i].F);
    }
    else
    {
      if(it1==n)
        l=n+1;
      else
        l=v1[j][it1].S.S.S;
      i=min(i,l);
      if(i!=0&&i!=n+1)
      mi1=min(mi1,s1[j][i].S);
    }
  }
  if(t==0||t==3)
  {
    if(ma1<=v3)
      return(1);
    else
      return(0);
  }
  else
  {
    if(mi1>=v3)
      return(1);
    else
      return(0);
  }
}
int solve(int v)
{
  int c=check(ma-v,3,mi+v);
  c=max(c,check(mi+v,2,ma-v));
  c=max(c,check(ma-v,0,mi+v));
  c=max(c,check(mi+v,1,ma-v));
  return(c);
}
int main()
{
  cin>>n>>m;
  for(int i=n;i>=1;--i)
    for(int j=1;j<=m;++j)
      cin>>arr[i][j];
  for(int j=1;j<=m;++j)
  {
    l1[j][0].F=0;
    s1[j][0].F=1000000200;
    for(int i=1;i<=n;++i)
    {
      ma=max(ma,arr[i][j]);
      mi=min(mi,arr[i][j]);
      v1[j].pb(mp(arr[i][j],mp(mp(i,i),mp(i,i))));
      l1[j][i].F=max(l1[j][i-1].F,arr[i][j]);
      s1[j][i].F=min(s1[j][i-1].F,arr[i][j]);
    }
    sort(all(v1[j]));
    for(int i=1;i<n;++i)
    {
      v1[j][i].S.F.F=max(v1[j][i-1].S.F.F,v1[j][i].S.F.F);
      v1[j][i].S.F.S=min(v1[j][i-1].S.F.S,v1[j][i].S.F.S);
    }
    l1[j][n+1].S=0;
    s1[j][n+1].S=1000000200;
    for(int i=n;i>=1;--i)
    {
      if(i!=n)
      {
        v1[j][i-1].S.S.F=max(v1[j][i].S.S.F,v1[j][i-1].S.S.F);
        v1[j][i-1].S.S.S=min(v1[j][i].S.S.S,v1[j][i-1].S.S.S);
      }
      l1[j][i].S=max(l1[j][i+1].S,arr[i][j]);
      s1[j][i].S=min(s1[j][i+1].S,arr[i][j]);
    }
  }
  int l=0,r=ma-mi,ans;
  ans=ma-mi;
  while(l<=r)
  {
    int mid=(l+r)/2;
    if(solve(mid))
    {
      r=mid-1;
      ans=min(ans,mid);
    }
    else
    {
      l=mid+1;
    }
  }
  cout<<ans<<endl;
  return 0;
}

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