URAL/1424

来自"NOCOW"

调map维护下就行。。

#include <cstdio>
#include <map>
#include <algorithm>
#define Delete if(!(--(it->second)))x.erase(it->first)
using namespace std;
int n,m,k,p,tot=0,ans=0;
struct node  {  int l,r,rank;  }v,t[50002];
map<node,int> x;
map<node,int>::iterator it;
bool used[50002]={false};
bool operator < (const node& a,const node& b)
{
    if (a.r == b.r)  return a.l < b.l;
    return a.r < b.r;
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&k,&p);
    for (int i=1;i<=k;t[i].rank=i++)
        scanf("%d%d",&t[i].l,&t[i].r);
    sort(&t[1],&t[k+1]);
    for (int i=1;i<=k;++i)
    {
        v.rank=t[i].rank,v.l=-1,v.r=t[i].l;
        it=x.upper_bound(v);
        v.l=-v.rank,v.r=t[i].r;
        bool null=(it==x.begin());
        if (!null)  --it;
        if (tot < m)
        {
            if (!null)  {  Delete;  --tot;  }
            ++x[v],++tot;
        }
        else if (!null)  {  Delete;  ++x[v];  }
        else  ++ans,used[t[i].rank]=true;
    }
    printf("%d\n",(k-ans)*p);
    for (int i=1;i<=k;++i)  if (!used[i])  printf("%d ",i);
    printf("\n");
    return 0;
}
//by zzy