题解：P11289 【MX-S6-T1】「KDOI-11」打印

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const ll N=2e5+10;
struct wq
{
	ll id,t;
	bool operator < (const wq &a)const
	{
		return t>a.t;
	}
}o;
ll cnt,n,m,t=1,id,temp[N];
priority_queue<ll,vector<ll>,greater<ll> > q;
priority_queue<wq> v;
vector<ll> vec[N];
struct node
{
	ll s,t,id;
}a[N];
bool cmp(node a,node b)
{
	return a.t<b.t;
}
ll read()
{
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x*=10,x+=c-'0';
		c=getchar();
	}
	return x*f;
}
inline void print(ll x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9)
	{
		print(x/10);
	}
	putchar(x%10+'0');
}
int main()
{
	freopen("print4.in","r",stdin);
	freopen("print.out","w",stdout);
	n=read(),m=read();
	for(ll i=1;i<=n;i++)
	{
		a[i].s=read();
		a[i].t=read();
		a[i].id=i;
	}
	sort(a+1,a+n+1,cmp);
	for(ll i=1;i<=m;i++)
	{
		q.push(i);
	}
	for(ll i=1;i<=n;i++)
	{
		t=max(a[i].t,t);
		while(!v.empty()&&v.top().t<=t)
		{
			q.push(v.top().id);
			v.pop();
		}
		if(q.empty()) t=v.top().t;
		while(!v.empty()&&v.top().t<=t)
		{
			q.push(v.top().id);
			v.pop();
		}
		id=q.top();
		q.pop();
		o.id=id,o.t=t+a[i].s;
		v.push(o);
		vec[id].push_back(a[i].id);
	}
	for(ll i=1;i<=m;i++)
	{
		print(vec[i].size());
		putchar(' ');
		ll len=vec[i].size();
		
		for(ll j=0;j<vec[i].size();j++) temp[j]=vec[i][j];
		sort(temp,temp+len);
		for(ll j=0;j<vec[i].size();j++) print(temp[j]),putchar(' ');
		putchar('\n');
	}
	
	
	return 0;
 }