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 Ryo_Yamada @ 2020-07-10 21:42:39
qndgxoi(
by gdjcwsk @ 2020-07-10 21:49:36
qndmx
by 蛙蛙 @ 2020-07-10 21:56:10
问乔某(我爬走了
by Ryo_Yamada @ 2020-07-10 22:04:55
问你npy@ws寂然
by gdjcwsk @ 2020-07-10 22:12:18
@ws寂然 出来看看
by Zoe_Granger @ 2020-07-10 22:12:54
@蛙蛙 (微笑
by 蛙蛙 @ 2020-07-10 22:19:29
@Zoe_Granger 我爬走了你不要过来啊
by michael_song @ 2020-07-10 22:55:27
qndmx
by monstersqwq @ 2020-07-10 23:07:38
stO Zoe Orz
by 不问人间烟雨 @ 2020-07-12 11:17:16
……?大家要干什么