Zoe_Granger @ 2020-07-10 21:41:45
第五个点一直是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;
}
by FishingStar @ 2021-01-24 20:31:50
Orz 神Zoe