WA on #1求助
查看原帖
WA on #1求助
523541
Onana_in_XMFLS楼主2022/7/13 11:54
// Problem: P7913 [CSP-S 2021] 廊桥分配
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7913
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
#define mem(arr,val) memset((arr),(val),(sizeof(arr)))
using namespace std;
const int maxn = 1e5+5;
struct ss{int st,ed;}a[maxn],b[maxn];
int ans1[maxn],ans2[maxn],s1[maxn],s2[maxn];
bool operator<(ss sb,ss sb2) {return sb.st < sb2.st;}
priority_queue <ss> full;
priority_queue <int> emp;
int main(int argc,char *argv[])
{
	int n,m1,m2;cin>>n>>m1>>m2;	
	for(int i = 1;i <= m1;++i) cin>>a[i].st>>a[i].ed;
	for(int i = 1;i <= m2;++i) cin>>b[i].st>>b[i].ed;
	sort(a+1,a+m1+1);sort(b+1,b+m2+1);
	for(int i = 1;i <= n;++i) emp.push(-i);
	for(int i = 1;i <= m1;++i)
	{
		int s = a[i].st,e = a[i].ed;
		while(!full.empty() && -(full.top().st) < s)
		{
			emp.push(-full.top().ed);
			full.pop();
		}
		if(!emp.empty())
		{
			int tmp = -emp.top();
			full.push({-e,tmp});
			++ans1[tmp];
			emp.pop();
		}
	}
	while(!full.empty()) full.pop();
	while(!emp.empty()) emp.pop();
	for(int i = 1;i <= n;++i) emp.push(-i);
	for(int i = 1;i <= m2;++i)
	{
		int s = b[i].st,e = b[i].ed;
		while(!full.empty() && -(full.top().st) < s)
		{
			emp.push(-full.top().ed);
			full.pop();
		}
		if(!emp.empty())
		{
			int tmp = -emp.top();
			full.push({-e,tmp});
			++ans2[tmp];
			emp.pop();
		}
	}
	for(int i = 1;i <= n;++i)
		s1[i] = s1[i-1]+ans1[i],
		s2[i] = s2[i-1]+ans2[i];
	int res = -1;
	for(int i = 1;i <= n;++i)
		res = max(res,s1[i]+s2[n-i]);
	cout<<res<<'\n';
	return 0;
}
2022/7/13 11:54
加载中...