oj.uz

Submission #978999

# Submission time Handle Problem Language Result Execution time Memory
978999 2024-05-10T05:42:56 Z 8pete8 The Kingdom of JOIOI (JOI17_joioi) C++17
100 / 100
 1775 ms 262144 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
#include <cstdlib> 
#include <cstdint>
using namespace std;
#define ll long long
#define f first
//#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
#define int long long
#define double long double
const int mxn=1e5,inf=1e18,minf=-1e18,Mxn=1e7;
int grid[3003][3003],bound[3003],grid2[3003][3003];//keep boundary on left comp
int mxbound[3003],mxrange=0;
bool have[3003];
int mx=minf,mn=inf;
vector<pii>mxpos,mnpos;
int n,m;
int solve(int mode){//1==mn on left
	vector<pair<int,pii>>v;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
		if(grid[i][j]!=mn&&grid[i][j]!=mx)v.pb({max(mx-grid[i][j],grid[i][j]-mn),{i,j}});
	}
	sort(rall(v));
	int amx=0;//another mx
	for(auto i:v){
		bool side=(mx-grid[i.s.f][i.s.s]>grid[i.s.f][i.s.s]-mn);//if 1 then we need to go to mn
		if(mx-grid[i.s.f][i.s.s]==grid[i.s.f][i.s.s]-mn)return mx-grid[i.s.f][i.s.s];
		if(i.f<amx)return amx;
		amx=max(amx,mxrange-i.f);
		side^=mode;
		if(side){
			//right
			if(bound[i.s.f]<i.s.s)mxbound[i.s.f]=min(i.s.s,mxbound[i.s.f]);//alrdy valid
			else return i.f;
			//we cant decrease the bound?
		}
		else{
			//left
			if(bound[i.s.f]>=i.s.s);//alrdy valid
			else{
				while(bound[i.s.f]<i.s.s){
					int cur=i.s.f,b=inf;
					while(cur>=1&&bound[cur]==bound[i.s.f])b=min(b,mxbound[cur]),cur--;
					if(bound[i.s.f]+1>=b)return i.f;
					for(int j=cur+1;j<=i.s.f;j++)bound[j]++;
				}
				//we can increase the bound
			}
		}
	}
	return amx;
}
int solvemain(){
	int ans=inf;
	mxpos.clear();
	mnpos.clear();
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
		if(grid[i][j]==mx)mxpos.pb({i,j});
		if(grid[i][j]==mn)mnpos.pb({i,j});
	}
	for(int i=1;i<=n;i++)bound[i]=0,mxbound[i]=m+1;
	bound[1]=1;//min bound (atleast one exist)
	mxbound[n]=m;
	for(auto i:mxpos)bound[i.f]=max(bound[i.f],i.s);
	for(int i=n;i>=1;i--)bound[i]=max(bound[i],bound[i+1]);
	bool valid=1;
	for(auto i:mnpos)valid&=(bound[i.f]<i.s),mxbound[i.f]=min(mxbound[i.f],i.s);
	if(valid)ans=min(ans,solve(0));
	//put mn of left comp
	for(int i=1;i<=n;i++)bound[i]=0,mxbound[i]=m+1;
	bound[1]=1;
	mxbound[n]=m;
	for(auto i:mnpos)bound[i.f]=max(bound[i.f],i.s);
	for(int i=n;i>=1;i--)bound[i]=max(bound[i],bound[i+1]);
	valid=1;
	for(auto i:mxpos)valid&=(bound[i.f]<i.s),mxbound[i.f]=min(mxbound[i.f],i.s);;
	if(valid)ans=min(ans,solve(1));
	return ans;
}
//will this work??????????
int32_t main(){
	fastio
	cin>>n>>m;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
		cin>>grid[i][j],mx=max(mx,grid[i][j]),mn=min(mn,grid[i][j]);
		grid2[i][m-j+1]=grid[i][j];
	}
	if(mx==mn)return cout<<0,0;
	mxrange=mx-mn;
	int ra=mx-mn;
	ra=min(ra,solvemain());
	swap(grid,grid2);
	ra=min(ra,solvemain());
	//put max on left comp and left comp is decreasing
	cout<<ra;
	return 0;
}
/*

greedy idea?:
we dont want the min and max value to be in the same component
if we can make the min and max not in the same comp the answer would just be max-min
so we will try seperating them
this will create a boundary line (depending on max is on the left or right comp)
when we have boundary line when can then greedy sort value by the contribution to the answer?
so sort by min(max-x,x-min) then we greedy if its really close to max then we will try putting it in max comp
which will also shape a new boundary then we keep repeating this?
if we cant put it into the respective comp then answer is abs(min/max-x)?

will this work??????
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 141608 KB Output is correct
2 Correct 88 ms 141392 KB Output is correct
3 Correct 64 ms 141396 KB Output is correct
4 Correct 59 ms 141576 KB Output is correct
5 Correct 62 ms 141644 KB Output is correct
6 Correct 61 ms 141396 KB Output is correct
7 Correct 63 ms 141596 KB Output is correct
8 Correct 61 ms 141568 KB Output is correct
9 Correct 68 ms 141648 KB Output is correct
10 Correct 60 ms 141396 KB Output is correct
11 Correct 59 ms 141648 KB Output is correct
12 Correct 58 ms 141448 KB Output is correct
13 Correct 67 ms 141648 KB Output is correct
14 Correct 67 ms 141648 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 141608 KB Output is correct
2 Correct 88 ms 141392 KB Output is correct
3 Correct 64 ms 141396 KB Output is correct
4 Correct 59 ms 141576 KB Output is correct
5 Correct 62 ms 141644 KB Output is correct
6 Correct 61 ms 141396 KB Output is correct
7 Correct 63 ms 141596 KB Output is correct
8 Correct 61 ms 141568 KB Output is correct
9 Correct 68 ms 141648 KB Output is correct
10 Correct 60 ms 141396 KB Output is correct
11 Correct 59 ms 141648 KB Output is correct
12 Correct 58 ms 141448 KB Output is correct
13 Correct 67 ms 141648 KB Output is correct
14 Correct 67 ms 141648 KB Output is correct
15 Correct 57 ms 141648 KB Output is correct
16 Correct 57 ms 141904 KB Output is correct
17 Correct 67 ms 144392 KB Output is correct
18 Correct 68 ms 144148 KB Output is correct
19 Correct 68 ms 144344 KB Output is correct
20 Correct 67 ms 144184 KB Output is correct
21 Correct 69 ms 144396 KB Output is correct
22 Correct 66 ms 144308 KB Output is correct
23 Correct 67 ms 144336 KB Output is correct
24 Correct 66 ms 144324 KB Output is correct
25 Correct 67 ms 144420 KB Output is correct
26 Correct 67 ms 144488 KB Output is correct
27 Correct 69 ms 144596 KB Output is correct
28 Correct 67 ms 144392 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 141608 KB Output is correct
2 Correct 88 ms 141392 KB Output is correct
3 Correct 64 ms 141396 KB Output is correct
4 Correct 59 ms 141576 KB Output is correct
5 Correct 62 ms 141644 KB Output is correct
6 Correct 61 ms 141396 KB Output is correct
7 Correct 63 ms 141596 KB Output is correct
8 Correct 61 ms 141568 KB Output is correct
9 Correct 68 ms 141648 KB Output is correct
10 Correct 60 ms 141396 KB Output is correct
11 Correct 59 ms 141648 KB Output is correct
12 Correct 58 ms 141448 KB Output is correct
13 Correct 67 ms 141648 KB Output is correct
14 Correct 67 ms 141648 KB Output is correct
15 Correct 57 ms 141648 KB Output is correct
16 Correct 57 ms 141904 KB Output is correct
17 Correct 67 ms 144392 KB Output is correct
18 Correct 68 ms 144148 KB Output is correct
19 Correct 68 ms 144344 KB Output is correct
20 Correct 67 ms 144184 KB Output is correct
21 Correct 69 ms 144396 KB Output is correct
22 Correct 66 ms 144308 KB Output is correct
23 Correct 67 ms 144336 KB Output is correct
24 Correct 66 ms 144324 KB Output is correct
25 Correct 67 ms 144420 KB Output is correct
26 Correct 67 ms 144488 KB Output is correct
27 Correct 69 ms 144596 KB Output is correct
28 Correct 67 ms 144392 KB Output is correct
29 Correct 865 ms 213380 KB Output is correct
30 Correct 815 ms 217076 KB Output is correct
31 Correct 923 ms 262144 KB Output is correct
32 Correct 825 ms 218484 KB Output is correct
33 Correct 925 ms 205472 KB Output is correct
34 Correct 924 ms 218684 KB Output is correct
35 Correct 1775 ms 262144 KB Output is correct
36 Correct 1755 ms 262144 KB Output is correct
37 Correct 1759 ms 262144 KB Output is correct