oj.uz

Submission #692507

# Submission time Handle Problem Language Result Execution time Memory
692507 2023-02-01T16:30:35 Z stonejjun03 The Kingdom of JOIOI (JOI17_joioi) C++14
100 / 100
 2239 ms 120956 KB 
#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

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 456 KB Output is correct
8 Correct 1 ms 456 KB Output is correct
9 Correct 0 ms 456 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 452 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 456 KB Output is correct
8 Correct 1 ms 456 KB Output is correct
9 Correct 0 ms 456 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 452 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 6 ms 3544 KB Output is correct
17 Correct 19 ms 4024 KB Output is correct
18 Correct 13 ms 4060 KB Output is correct
19 Correct 18 ms 4084 KB Output is correct
20 Correct 18 ms 3644 KB Output is correct
21 Correct 20 ms 4208 KB Output is correct
22 Correct 15 ms 4176 KB Output is correct
23 Correct 18 ms 4212 KB Output is correct
24 Correct 12 ms 3756 KB Output is correct
25 Correct 18 ms 4176 KB Output is correct
26 Correct 20 ms 4176 KB Output is correct
27 Correct 20 ms 4188 KB Output is correct
28 Correct 20 ms 4200 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 456 KB Output is correct
8 Correct 1 ms 456 KB Output is correct
9 Correct 0 ms 456 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 452 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 6 ms 3544 KB Output is correct
17 Correct 19 ms 4024 KB Output is correct
18 Correct 13 ms 4060 KB Output is correct
19 Correct 18 ms 4084 KB Output is correct
20 Correct 18 ms 3644 KB Output is correct
21 Correct 20 ms 4208 KB Output is correct
22 Correct 15 ms 4176 KB Output is correct
23 Correct 18 ms 4212 KB Output is correct
24 Correct 12 ms 3756 KB Output is correct
25 Correct 18 ms 4176 KB Output is correct
26 Correct 20 ms 4176 KB Output is correct
27 Correct 20 ms 4188 KB Output is correct
28 Correct 20 ms 4200 KB Output is correct
29 Correct 1046 ms 62144 KB Output is correct
30 Correct 1035 ms 85672 KB Output is correct
31 Correct 1114 ms 88264 KB Output is correct
32 Correct 1119 ms 88248 KB Output is correct
33 Correct 574 ms 77308 KB Output is correct
34 Correct 1095 ms 88360 KB Output is correct
35 Correct 2223 ms 120956 KB Output is correct
36 Correct 1496 ms 88716 KB Output is correct
37 Correct 2239 ms 96532 KB Output is correct