Submission #50711

#	Time	Username	Problem	Language	Result	Execution time	Memory
50711		MatheusLealV	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	3964 ms	289636 KiB

joioi

#include <bits/stdc++.h>
#define N 2050
using namespace std;

struct ponto {
	int x, y, val;
};

vector < ponto > P;

bool op(ponto a, ponto b){
	return a.val < b.val;
}

int n, m, mat[N][N], A[N][N], B[N][N];

int rightmost(int val)
{
	int ini = 0, fim = P.size() - 1, mid, best;

	while(fim >= ini)
	{
		mid = (ini + fim)/2;

		if(P[mid].val - P[0].val <= val) ini = mid + 1, best = mid;

		else fim = mid - 1;
	}

	return best;
}

int leftmost(int val)
{
	int ini = 0, fim = P.size() - 1, mid, best;

	while(fim >= ini)
	{
		mid = (ini + fim)/2;

		if(P.back().val - P[mid].val <= val) fim = mid - 1, best = mid;

		else ini = mid + 1;
	}

	return best;
}

int queryA(int xi, int yi, int xii, int yii) {
	return A[xii][yii] - A[xii][yi - 1] - A[xi - 1][yii] + A[xi - 1][yi - 1];
}

int queryB(int xi, int yi, int xii, int yii) {
	return B[xii][yii] - B[xii][yi - 1] - B[xi - 1][yii] + B[xi - 1][yi - 1];
}

int M[N][N], M2[N][N];

bool check1() // INDEXADO NA ESQUERDA-CIMA
{
	bool E = 1, D = 1;

	int maior = 0;

	for(int i = n; i >= 1; i--)
	{
		for(int j = 1; j <= m; j++)
			if(A[i][j]) maior = max(maior, j);

		for(int j = 1; j <= maior; j++)
			if(B[i][j]) E = 0;
	}

	maior = 0;

	for(int i = n; i >= 1; i--)
	{
		for(int j = 1; j <= m; j++)
			if(B[i][j]) maior = max(maior, j);

		for(int j = 1; j <= maior; j++)
			if(A[i][j]) D = 0;
	}

	return (E || D);
}

bool check2() // INDEXADO NA ESQUERDA-BAIXO
{
	int maior = 0, E = 1, D = 1;

	for(int i = 1; i <= n; i ++)
	{
		for(int j = 1; j <= m; j++)
			if(A[i][j]) maior = max(maior, j);

		for(int j = 1; j <= maior; j++)
			if(B[i][j]) E = 0;
	}

	maior = 0;

	for(int i = 1; i <= n; i ++)
	{
		for(int j = 1; j <= m; j++)
			if(B[i][j]) maior = max(maior, j);

		for(int j = 1; j <= maior; j++)
			if(A[i][j]) D = 0;
	}

	return (E || D);
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>m;

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin>>mat[i][j], P.push_back({i, j, mat[i][j]});

	sort(P.begin(), P.end(), op);

	int ini = 0, fim = 1e9, mid, best = -1;

	while(fim >= ini)
	{
		mid = (ini + fim)/2;

		int L = leftmost(mid), R = rightmost(mid);

		memset(A, 0, sizeof A), memset(B, 0, sizeof B);

		memset(M, 0, sizeof M);

		if(L <= R || R == L - 1)
		{
			if(R == L - 1) swap(L, R);

			for(int i = 0; i < L; i++)
			{
				int x = P[i].x, y = P[i].y;

				A[x][y] ++;
			}

			for(int i = R + 1; i < P.size(); i++)
			{
				int x = P[i].x, y = P[i].y;

				B[x][y] ++;
			}

			if(check1() || check2())
			{
				best = mid;

				fim = mid - 1;
			}

			else ini = mid + 1;

			/*for(int i = 1; i <= n; i++)
				for(int j = 1; j <= m; j++)
				{
					A[i][j] += A[i - 1][j] + A[i][j - 1] - A[i - 1][j - 1];

					B[i][j] += B[i - 1][j] + B[i][j - 1] - B[i - 1][j - 1];
				}*/
		}

		else ini = mid + 1;
	}

	cout<<best<<"\n";
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:150:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = R + 1; i < P.size(); i++)
                       ~~^~~~~~~~~~
joioi.cpp: In function 'int rightmost(int)':
joioi.cpp:30:9: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return best;
         ^~~~
joioi.cpp: In function 'int leftmost(int)':
joioi.cpp:46:9: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return best;
         ^~~~

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