[JZOJ 5861] 失意

思路：

求交集最大老套路，排序之后用堆维护即可。
#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9+7;

const int maxn = 1000010;

inline int read() {

	int q=0,f=1;char ch = getchar();

	while(!isdigit(ch)){

		if(ch=='-')f=-1;ch=getchar();

	}

	while(isdigit(ch)){

		q=q*10+ch-'0';ch=getchar();

	}

	return q*f;

}

struct lne {

	int l,r,id;

	bool operator < (lne x) const{

		return r > x.r;

	}

}l[maxn];

int ans;

int n,m;

priority_queue<lne> q;

bitset<maxn>vis,p;

int siz;

inline bool cmp(lne a,lne b) {

	return (a.l == b.l) ? (a.r > b.r) : (a.l < b.l);

}

int main () {

	freopen("failure.in","r",stdin);

	freopen("failure.out","w",stdout);

	read();

	n = read(),m = read();

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

		l[i].l = read();

		l[i].r = read();

		l[i].id = i;

	}

	sort(l + 1,l + n + 1,cmp);

	for(int i = 1;i <= m; ++i) {

		q.push(l[i]);

		++siz;

		vis[l[i].id] = 1;

	}

	lne top = q.top();

	ans = max(top.r - l[m].l,0);

	p = vis;

	for(int i = m + 1;i <= n; ++i) {

		q.push(l[i]);

		++siz;

		vis[l[i].id] = 1;

		if(siz > m) {

			top = q.top();

			vis[top.id] = 0;

			q.pop();

			siz--;

		}

		if(siz == m) {

			top = q.top();

			int len = max(top.r - l[i].l,0);

			if(len >= ans) {

				ans = len;

				p = vis;

			}

		}

	}

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

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

		if(p[i]) {

			printf("%d ",i);

		}

	}

	return 0;

}
巴特西

[JZOJ 5861] 失意

最新文章

热门文章
