Submission #95841

#	Time	Username	Problem	Language	Result	Execution time	Memory
95841		diamond_duke	Cultivation (JOI17_cultivation)	C++11	100 / 100	1257 ms	1144 KiB

cultivation

#include <algorithm>
#include <cstdio>
using ll = long long;
std::pair<ll, int> imp[605];
struct motonic_queue
{
	int que[605], *arr, he, ta;
	motonic_queue(int *_arr) : arr(_arr), he(0), ta(-1) {}
	inline void pop(int pos)
	{
		while (he <= ta && que[he] < pos)
			he++;
	}
	inline void push(int pos)
	{
		while (he <= ta && arr[imp[pos].second] >= arr[imp[que[ta]].second])
			ta--;
		que[++ta] = pos;
	}
	inline ll front() { return arr[imp[que[he]].second]; }
};
struct point { ll x, y; } arr[305];
int idx[305], lp[305], rp[305], H, W, n, cnt;
int sum[200005], A[605], B[605], C[605];
bool vis[605][305];
inline void add(int x, int y)
{
	vis[x][y] = true;
	int lst = -1;
	A[x] = B[x] = C[x] = 0;
	for (int i = 0; i < n; i++)
	{
		y = idx[i];
		if (!vis[x][y])
			continue;
		if (-1 == lst)
			A[x] = arr[y].y - 1;
		else
			B[x] = std::max<int>(B[x], arr[y].y - lst - 1);
		lst = arr[y].y;
	}
	C[x] = W - lst;
}
inline ll solve()
{
	motonic_queue que_A(A), que_B(B), que_C(C);
	ll ans = W * 2;
	for (int i = 0, j = 0; i < n * 2 && imp[i].first + H <= imp[n * 2 - 1].first; i++)
	{
		que_A.pop(i);
		que_B.pop(i);
		que_C.pop(i);
		while (j < n * 2 && imp[i].first + H > imp[j].first)
		{
			que_A.push(j);
			que_B.push(j);
			que_C.push(j);
			j++;
		}
		ans = std::min(ans, std::max(que_A.front() + que_C.front(), que_B.front()));
	}
	return ans;
}
int main()
{
	// freopen("loj-2390.in", "r", stdin);
	scanf("%d%d%d", &H, &W, &n);
	for (int i = 0; i < n; i++)
		scanf("%lld%lld", &arr[i].x, &arr[i].y);
	std::sort(arr, arr + n, [&] (point a, point b) { return a.x < b.x; });
	sum[cnt++] = arr[0].x - 1 + H - arr[n - 1].x;
	for (int i = 1; i < n; i++)
		sum[0] = std::max<int>(sum[0], arr[i].x - arr[i - 1].x - 1);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (i == j)
				continue;
			if (sum[0] < arr[i].x - arr[j].x - 1 + H)
				sum[cnt++] = arr[i].x - arr[j].x - 1 + H;
			if (i > j && sum[0] < arr[i].x - arr[j].x - 1)
				sum[cnt++] = arr[i].x - arr[j].x - 1;
		}
	}
	std::sort(sum, sum + cnt);
	cnt = std::unique(sum, sum + cnt) - sum;
	for (int i = 0; i < n; i++)
		idx[i] = i;
	std::sort(idx, idx + n, [&] (int x, int y) { return arr[x].y < arr[y].y; });
	ll ans = 1e18;
	for (int i = 0; i < cnt; i++)
	{
		for (int j = 0; j < n; j++)
		{
			while (lp[j] < n && arr[j].x + sum[i] >= arr[lp[j]].x)
			{
				if (arr[j].x <= arr[lp[j]].x)
					add(lp[j], j);
				lp[j]++;
			}
			while (rp[j] < n && arr[j].x + sum[i] + 1 >= arr[rp[j]].x)
			{
				if (arr[j].x < arr[rp[j]].x)
					add(j + n, rp[j]);
				rp[j]++;
			}
			imp[j] = {arr[j].x, j};
			imp[j + n] = {arr[j].x + sum[i] + 1, j + n};
		}
		std::merge(imp, imp + n, imp + n, imp + n + n, imp);
		ans = std::min(ans, sum[i] + solve());
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

cultivation.cpp: In function 'int main()':
cultivation.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &H, &W, &n);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &arr[i].x, &arr[i].y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 20 / 20
• Subtask 6: 20 / 20