T538784

先对命令按照 t_i 升序进行排序，方便处理。

我们定义 pre_i 为这个打印机最后打印的时刻。

当对于所有的 j 满足 1\le j \le n 的 pre_j 的最小值 k 满足 k \le t_i 时，则我们找到最小的 j，使得 pre_j\le t_i，然后把 j 号打印机最后打印的时刻修改为 s_i+t_i，同时让 i 号指令给到 j 号打印机。

否则，我们找到 pre 数组里面最前面的 k，设其下表为 j，把 j 号打印机的打印的最后时刻修改为 s_i+k，同时让 i 号指令给到 j 号打印机。

用线段树简单维护最小值以及单点修改即可。查找可以使用二分。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5,inf=0x3f3f3f3f3f3f3f3f;
vector<int>ans[N];
int tr[N<<2];
struct node{int s,t,id;}a[N];
bool cmp(node n1,node n2){return n1.t<n2.t;}
void pushup(int p){tr[p]=min(tr[p<<1],tr[p<<1|1]);}
void update(int p,int pl,int pr,int x,int d)
{
    if(x<pl||pr<x)
        return;
    if(pl==pr)
    {
        tr[p]+=d;
        return;
    }
    int mid=(pl+pr)>>1;
    update(p<<1,pl,mid,x,d);
    update(p<<1|1,mid+1,pr,x,d);
    pushup(p);
}
void change(int p,int pl,int pr,int x,int d)
{
    if(x<pl||pr<x)
        return;
    if(pl==pr)
    {
        tr[p]=d;
        return;
    }
    int mid=(pl+pr)>>1;
    change(p<<1,pl,mid,x,d);
    change(p<<1|1,mid+1,pr,x,d);
    pushup(p);
}
int query(int p,int pl,int pr,int L,int R)
{
    if(R<pl||pr<L)
        return inf;
    if(L<=pl&&pr<=R)
        return tr[p];
    int mid=(pl+pr)>>1;
    return min(query(p<<1,pl,mid,L,R),query(p<<1|1,mid+1,pr,L,R));
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i].s>>a[i].t,a[i].id=i;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;++i)
    {
        // cout<<'\n';
        int l=0,r=m+1,k=tr[1];
        if(k<=a[i].t)
        {
            while(l+1<r)
            {
                int mid=(l+r)>>1;
                if(query(1,1,m,1,mid)<=a[i].t)
                    r=mid;
                else
                    l=mid;
            }
            change(1,1,m,r,a[i].t+a[i].s);
            ans[r].emplace_back(a[i].id);
        }
        else
        {
            while(l+1<r)
            {
                int mid=(l+r)>>1;
                if(query(1,1,m,1,mid)==k)
                    r=mid;
                else
                    l=mid;
            }
            update(1,1,m,r,a[i].s);
            ans[r].emplace_back(a[i].id);
        }
    }
    for(int i=1;i<=m;i++)
    {
        sort(ans[i].begin(),ans[i].end());
        cout<<ans[i].size()<<' ';
        for(auto &j:ans[i])
            cout<<j<<" ";
        cout<<'\n';
    }
}