求调过不了样例
查看原帖
求调过不了样例
377873
EricWan楼主2025/1/9 23:06
#include <bits/stdc++.h>
#define int long long
#define MAXN 1000005
using namespace std;
int n, m, k, a[2][MAXN], b[2][MAXN], dp[MAXN][2][2];
pair<int, int> A[MAXN];
signed main()
{
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> A[i].first >> A[i].second;
	}
	sort(A + 1, A + n + 1);
	for (int i = 1; i <= n; i++)
	{
		a[0][i] = A[i].first;
		b[0][i] = A[i].second - 1;
	}
	for (int i = 1; i <= m; i++)
	{
		cin >> A[i].first >> A[i].second;
	}
	sort(A + 1, A + m + 1);
	for (int i = 1; i <= m; i++)
	{
		a[1][i] = A[i].first;
		b[1][i] = A[i].second - 1;
	}
	a[0][n + 1] = 2000000000;
	b[0][n + 1] = 2000000000;
	a[1][m + 1] = 2000000000;
	b[1][m + 1] = 2000000000;
	memset(dp, 0x3f, sizeof(dp));
	dp[!a[0][1]][0][0] = 0;
	for (int i = 0; i <= n + m; i++)
	{
		if (dp[i][0][0] <= 1000000000)
		{
			int nxtc = upper_bound(a[0] + 1, a[0] + n + 1, dp[i][0][0]) - a[0];
			int nowc = nxtc - 1;
			if (nxtc < n)
			{
				dp[i + 1][0][0] = min(dp[i + 1][0][0], a[0][nxtc]);
			}
		}
		if (dp[i][1][0] <= 1000000000)
		{
			int nxtc = upper_bound(a[1] + 1, a[1] + m + 1, dp[i][1][0]) - a[1];
			int nowc = nxtc - 1;
			if (nxtc < m)
			{
				dp[i + 1][1][0] = min(dp[i + 1][1][0], a[1][nxtc]);
			}
		}
		if (dp[i][0][1] <= 1000000000)
		{
			int nxtc = upper_bound(a[0] + 1, a[0] + n + 1, dp[i][0][1]) - a[0];
			int nxto = upper_bound(a[1] + 1, a[1] + m + 1, dp[i][0][1]) - a[1];
			int nowc = nxtc - 1;
			int nowo = nxto - 1;
			int useo = upper_bound(a[1] + 1, a[1] + m + 1, max(dp[i][0][1] + k, b[1][nowo])) - a[1];
			if (useo < m)
			{
				dp[i + 1][1][min(dp[i][0][1] + k, a[1][useo]) <= b[0][nowc]] = max(dp[i + 1][1][min(dp[i][0][1] + k, a[1][useo]) <= b[0][nowc]], min(dp[i][0][1] + k, a[1][useo]));
			}
		}
		if (dp[i][1][1] <= 1000000000)
		{
			int nxtc = upper_bound(a[1] + 1, a[1] + m + 1, dp[i][1][1]) - a[1];
			int nxto = upper_bound(a[0] + 1, a[0] + n + 1, dp[i][1][1]) - a[0];
			int nowc = nxtc - 1;
			int nowo = nxto - 1;
			int useo = upper_bound(a[0] + 1, a[0] + n + 1, max(dp[i][1][1] + k, b[0][nowo])) - a[0];
			if (useo < m)
			{
				dp[i + 1][0][min(dp[i][1][1] + k, a[0][useo]) <= b[1][nowc]] = max(dp[i + 1][0][min(dp[i][1][1] + k, a[0][useo]) <= b[1][nowc]], min(dp[i][1][1] + k, a[0][useo]));
			}
		}
	}
	for (int i = n + m; i >= 0; i--)
	{
		if (dp[i][0][0] <= 1000000000)
		{
			cout << i;
			return 0;
		}
		if (dp[i][0][1] <= 1000000000)
		{
			cout << i;
			return 0;
		}
		if (dp[i][1][0] <= 1000000000)
		{
			cout << i;
			return 0;
		}
		if (dp[i][1][1] <= 1000000000)
		{
			cout << i;
			return 0;
		}
	}
	cout << 0;
	return 0;
}
2025/1/9 23:06
加载中...