蒟蒻刚学OI,90求助

P3740 [HAOI2014] 贴海报

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

……?大家要干什么


| 下一页