70pts代码求优化!!
查看原帖
70pts代码求优化!!
411019
许江一墨楼主2022/4/21 18:03

rt,代码如下:

#include <bits/stdc++.h>
#define gc getchar
#define MAXN (100000 + 157)
#define MAXM (200000 + 157)
#define ll long long

using namespace std;

ll n, m1, m2, k1, k2, cnt, ans = -MAXM;
ll a[MAXM];
ll b[MAXN], c[MAXN], sum_b[MAXN], sum_c[MAXN];
bool vis[MAXN];


template <typename T> inline void read(T &x) {
	x=0;int f=1;char ch=gc();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=gc();}
	x*=f;
}

struct edge {
	ll l, r;
}e1[MAXN], e2[MAXN];

bool inline cmp(edge x, edge y) {
	return x.l < y.l;
}

int main() {
// 	freopen("airport.in", "r", stdin);
// 	freopen("airport.out", "w", stdout);
	
	read(n), read(m1), read(m2);
	
	for(int i = 1; i <= m1; ++i) {
		read(a[++cnt]); e1[i].l = a[cnt]; 
		read(a[++cnt]); e1[i].r = a[cnt];
	}
	for(int i = 1; i <= m2; ++i) {
		read(a[++cnt]); e2[i].l = a[cnt]; 
		read(a[++cnt]); e2[i].r = a[cnt]; 
	}

	sort(e1 + 1, e1 + 1 + m1, cmp); 
	sort(e2 + 1, e2 + 1 + m2, cmp); 
	
	ll size = m1, last = 0, tmp = 0, l = 0, r = 0;
	k1 = k2 = 1;
	
	while(size > 0) {
		l = r = last = 0;
		tmp = 0;
		for(int i = 1; i <= m1; ++i) {
			l = e1[i].l, r = e1[i].r;
			if(l < last || vis[i]) continue;
			else {
				++tmp;
				vis[i] = 1;
				last = r;
			}
		}
		b[k1] = tmp;
		sum_b[k1] = sum_b[k1-1] + b[k1];
		size -= tmp;
		++k1;
	}
	--k1;
	
	size = m2, last = l = r = tmp = 0;
	memset(vis, 0, sizeof(vis));
	
	while(size > 0) {
		tmp = last = l = r = 0;
		for(int i = 1; i <= m2; ++i) {
			l = e2[i].l, r = e2[i].r;
			if(l < last || vis[i]) continue;
			else {
				++tmp;
				vis[i] = 1;
				last = r;
			}
		}
		c[k2] = tmp;
		sum_c[k2] = sum_c[k2-1] + c[k2];
		size -= tmp;
		++k2;
	}
	--k2;
	
	if(k1 + k2 <= n) {
	    cout << m1 + m2 << endl;
	    return 0;
	}
	
	for(int i = 0; i <= k1; ++i) {
		for(int j = 0; j <= k2; ++j) {
			if(i + j != n) continue;
			ans = max(ans, sum_b[i] + sum_c[j]);
		}
	}
	
	printf("%lld\n", ans);
	return 0;
}

子任务#0 TLE了6个点,子任务#1 全T....

请问有没有救....

求助!!

2022/4/21 18:03
加载中...