제출 #69424

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69424		MrTEK	The Kingdom of JOIOI (JOI17_joioi)	C++14	0 / 100	2 ms	376 KiB

joioi

#include <bits/stdc++.h>

using namespace std;
#define mp make_pair
#define pb push_back
#define len(a) (int)a.size()
#define fi first
#define sc second
#define d1(w) cerr<<#w<<":"<<w<<endl;
#define d2(w,c) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<endl;
#define d3(w,c,z) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<" "<<#z<<":"<<z<<endl;
#define left isc+isc
#define right isc+isc+1
#define mid (l+r)/2
#define FAfi_IO ios_base::sync_with_fidio(false);
#define escl '\n'

typedef long long int ll;

const int maxn = 620;
const long long LINF = 1e18;
const int LOG = 31;
const int INF = 1e9;
const int N = 2e3 + 5;
const int M = 1e4 + 5;
const int SQ = 350;
const int MOD = 998244353;

typedef long long int lli;
typedef pair<int,int> pii;

vector <pair <int,pii> > v;

deque <pair <int,pii> > Q;

pair <int,pii> temp[2];

int n,m,a[N][N],mnn[N][2],mxn[N][2],mnm[N][2],mxm[N][2];

bool check(int l1,int r1,int l2,int r2) {
	if (l2 > l1 && l2 < r1) return true;
	if (r2 > l1 && r2 < r1) return true;
	if (l1 > l2 && l1 < r2) return true;
	if (r1 > l2 && r1 < r2) return true;	
	return false;
}

int main() {
	scanf("%d %d",&n,&m);
	for (int i = 1 ; i <= n ; i++)
		for (int j = 1 ; j <= m ; j++) {
			scanf("%d",&a[i][j]);
			v.pb(mp(a[i][j],mp(i,j)));
		}
	for (int i = 1 ; i <= n ; i++)
		for (int j = 0 ; j < 2 ; j++)
			mnn[i][j] = INF , mxn[i][j] = -INF;

	for (int i = 1 ; i <= m ; i++)
		for (int j = 0 ; j < 2 ; j++)
			mnm[i][j] = INF , mxm[i][j] = -INF;

	sort(v.begin(),v.end());
	for (auto i : v)
		Q.push_back(i);

	temp[0] = Q.front();
	temp[1] = Q.back();
	for (int i = 0 ; i < 2 ; i++) {
		mnn[temp[i].sc.fi][i] = temp[i].sc.sc;
		mxn[temp[i].sc.fi][i] = temp[i].sc.sc;
		mnm[temp[i].sc.sc][i] = temp[i].sc.fi;
		mxm[temp[i].sc.sc][i] = temp[i].sc.fi;	
	}
	Q.pop_front(); Q.pop_back();
	while(len(Q)) {
		auto tutmn = Q.front();
		auto tutmx = Q.back();
		if (temp[1].fi - tutmn.fi >= tutmx.fi - temp[0].fi) {
			int val = tutmn.fi, i = tutmn.sc.fi, j = tutmn.sc.sc;
			mnn[i][0] = min(mnn[i][0],j);
			mxn[i][0] = max(mxn[i][0],j);
			mnm[j][0] = min(mnm[j][0],i);
			mxm[j][0] = max(mxm[j][0],i);
			if (check(mnn[i][0],mxn[i][0],mnn[i][1],mxn[i][1]) || check(mnm[j][0],mxm[j][0],mnm[j][1],mxm[j][1])) {
				printf("%d\n",temp[1].fi - val);
				return 0;
			}
			Q.pop_front();
		}
		else {
			int val = tutmx.fi, i = tutmx.sc.fi, j = tutmx.sc.sc;
			mnn[i][1] = min(mnn[i][1],j);
			mxn[i][1] = max(mxn[i][1],j);
			mnm[j][1] = min(mnm[j][1],i);
			mxm[j][1] = max(mxm[j][1],i);
			Q.pop_back();	
			if (check(mnn[i][0],mxn[i][0],mnn[i][1],mxn[i][1]) || check(mnm[j][0],mxm[j][0],mnm[j][1],mxm[j][1])) {
				printf("%d\n",val - temp[0].fi);
				return 0;
			}
		}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

joioi.cpp: In function 'int main()':
joioi.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
joioi.cpp:52:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&a[i][j]);
    ~~~~~^~~~~~~~~~~~~~~

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