蒟蒻刚学OI,90求助
查看原帖
蒟蒻刚学OI,90求助
192376
Zoe_Granger楼主2020/7/10 21:41

第五个点一直是WA,求神犇帮看看代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define LL long long
using namespace std;

const int MAXM = 1000+10;
const int MAXN = 1e7+10;

int n, m, l[MAXM], r[MAXM], a[3*MAXM], t[2*MAXM];
bool cover[100*MAXN];

inline int lc(int p) { return p<<1; }
inline int rc(int p) { return p<<1|1; }

void pushUp(int p)
{
	cover[p] = cover[lc(p)] && cover[rc(p)];
}

//true:完全覆盖
bool f(int p, int l, int r, int ql, int qr)
{
	if (cover[p])
		return true;
	bool ans = true;
	if (ql<=l && r<=qr)
	{
		ans = cover[p];
		cover[p] = true;
		return ans;
	}
	
	int mid = (l+r)>>1;
	if (ql<=mid)
		if (!f(lc(p), l, mid, ql, qr))
			ans = false;
	if (mid<qr)
		if (!f(rc(p), mid+1, r, ql, qr))
			ans = false;
	pushUp(p);
	return ans;
}

int main()
{
	scanf ("%d%d", &n, &m);
	for (int i=1; i<=m; i++)
	{
		scanf ("%d%d", &l[i], &r[i]);
		a[2*i-1] = l[i];
		a[2*i] = r[i];
	}
	
	sort (a+1, a+2*m+1);
	int un = unique(a+1, a+2*m+1)-(a+1);
	int cnt = 1;
	for (int i=1; i<un; i++)
	{
		t[a[i]] = cnt;
		if (a[i+1]-a[i] == 1)
			cnt++;
		else
			cnt+=2;
	}
	t[a[un]] = cnt;
	
	int sum=0;
	for (int i=m; i>=1; i--)
		if (!f(1, 1, cnt, t[l[i]], t[r[i]]))
			sum++;
	printf ("%d", sum);
	return 0;
}

2020/7/10 21:41
加载中...