Submission #692507

#	Time	Username	Problem	Language	Result	Execution time	Memory
692507		stonejjun03	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	2239 ms	120956 KiB

joioi

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long double dl;
typedef pair<dl,dl> pdi;
typedef pair<ll,ll> pii;
typedef pair<ll,pii> piii;

#define ff first
#define ss second
#define eb emplace_back
#define ep emplace
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) lower_bound(all(v), x) - v.begin()
//cout<<fixed;
//cout.precision(12);

ll n,m;
ll fld[2020][2020];
ll ldp[2020][2020];
ll rdp[2020][2020];
ll rm1[1010101];
ll lm1[1010101];
ll rm2[1010101];
ll lm2[1010101];

vector<ll> x;
vector<ll> y;

bool can(ll l,ll r){
	ll i,j;

	for(i=0;i<=n+1;i++){
		for(j=0;j<=m+1;j++)
			ldp[i][j]=rdp[i][j]=0;
		ldp[i][0]=rdp[i][m+1]=3;
	}

	for(i=1;i<=n;i++){
		lm1[i]=lm2[i]=1e9;
		rm1[i]=rm2[i]=-1;
	}

	//cout<<"yaho"<<endl;
	for(i=1;i<=n;i++){
	//cout<<"yaho"<<endl;
		for(j=1;j<=m;j++){
			if(fld[i][j]<=l) ldp[i][j]+=1;
			if(fld[i][j]>=r) ldp[i][j]+=2;
			ldp[i][j]&=ldp[i][j-1];
		}
	//cout<<"yaho"<<endl;

		for(j=m;j>=1;j--){
			if(fld[i][j]<=l) rdp[i][j]+=2;
			if(fld[i][j]>=r) rdp[i][j]+=1;
			rdp[i][j]&=rdp[i][j+1];
		}

		//for(j=0;j<=m+1;j++)
		//	cout<<i<<' '<<j<<' '<<ldp[i][j]<<' '<<rdp[i][j]<<'\n';

	//cout<<"yaho"<<endl;
		for(j=0;j<=m;j++){
			if(ldp[i][j]&rdp[i][j+1]&1) lm1[i]=min(lm1[i],j);
			if(ldp[i][j]&rdp[i][j+1]&2) lm2[i]=min(lm2[i],j);
			if(ldp[i][j]&rdp[i][j+1]&1) rm1[i]=max(rm1[i],j);
			if(ldp[i][j]&rdp[i][j+1]&2) rm2[i]=max(rm2[i],j);
		}

		//cout<<i<<' '<<lm1[i]<<' '<<lm2[i]<<' '<<rm1[i]<<' '<<rm2[i]<<'\n';
		if(i!=1){
			if(lm1[i-1]>rm1[i]) lm1[i-1]=1e9;
			if(lm2[i-1]>rm2[i]) lm2[i-1]=1e9;

			if(rm1[i-1]<lm1[i]) rm1[i-1]=-1;
			if(rm2[i-1]<lm2[i]) rm2[i-1]=-1;
		}
		if(i!=1){
			lm1[i]=max(lm1[i],lm1[i-1]);
			lm2[i]=max(lm2[i],lm2[i-1]);
			rm1[i]=min(rm1[i],rm1[i-1]);
			rm2[i]=min(rm2[i],rm2[i-1]);
		}
		//cout<<i<<' '<<lm1[i]<<' '<<lm2[i]<<' '<<rm1[i]<<' '<<rm2[i]<<'\n';
	//cout<<"yaho"<<endl;
	}

	if(lm1[n]<=m||lm2[n]<=m||rm1[n]>=0||rm2[n]>=0)
		return true;
	return false;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	cin>>n>>m;
	ll i,j,k;

	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++){
			cin>>fld[i][j];
			x.pb(fld[i][j]);
		}

	compress(x);
	ll sz=x.size();
	ll ans=x[sz-1];

	for(i=0;i<sz;i++)
		y.pb(x[i]-x[0]);

	for(i=1;i<sz-1;i++)
		y.pb(x[sz-1]-x[i]);
	compress(y);

	ll lo=0,hi=y.size();
	while(lo<hi){
		ll mi=(lo+hi)/2;
		ll mid=y[mi];
		ll l=x[0]+mid;
		ll r=x[sz-1]-mid;
		ll lidx=upper_bound(x.begin(), x.end(),l)-x.begin();
		ll ridx=lower_bound(x.begin(), x.end(),r)-x.begin();

		//cout<<lo<<' '<<hi<<' '<<mi<<' '<<mid<<' '<<l<<' '<<r<<' '<<lidx<<' '<<ridx<<endl;

		if(lidx<ridx){
			lo=mi+1;
			continue;
		}

		if(can(l,r)){
			hi=mi;
			ans=min(ans,mid);
		}
		else lo=mi+1;
	}

	cout<<ans;

}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:101:9: warning: unused variable 'k' [-Wunused-variable]
  101 |  ll i,j,k;
      |         ^

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