Codeforces 1249 D2. Too Many Segments (hard version)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

传送门

贪心

对于第一个不合法的位置，我们显然要通过删除几个覆盖了它的区间来使这个位置合法

显然删右端点更靠右的区间是更优的，所以就考虑优先删右端点靠右的，然后再考虑下一个不合法位置

用一个 $set$ 维护一下右端点和区间编号即可

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<vector>

#include<set>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=2e5+;

int n,m;

struct dat {

    int r,id;

    dat (int _r=,int _id=) { r=_r,id=_id; }

    inline bool operator < (const dat &tmp) const {

        return r!=tmp.r ? r<tmp.r : id<tmp.id;

    }

};

vector <dat> V[N];

vector <int> mov;

set <dat> S;

int main()

{

    n=read(),m=read(); int a,b,mx=;

    for(int i=;i<=n;i++)

        a=read(),b=read(),

        mx=max(mx,b),

        V[a].push_back(dat(b,i));

    int ans=;

    for(int i=;i<=mx;i++)

    {

        while(S.size()&&(*S.begin()).r<i) S.erase(S.begin());

        for(auto x: V[i]) S.insert(dat(x.r,x.id));

        while(S.size()>m)

        {

            auto p=S.rbegin();

            ans++,mov.push_back((*p).id);

            S.erase(*p);

        }

    }

    printf("%d\n",ans);

    for(auto x: mov) printf("%d ",x); puts("");

    return ;

}