前言

好题，总共用了 7 小时，打了 5k 代码。

本题解将讲一个 $O(n2^n\log n)$ 的方法。

思路

考虑 $P=1$ 的情况，发现可以通过状压解决，即设 $f_i$ 为当一张护照获得签证集合为 $i$ 时护照最早能够自由支配的时间，若不考虑任何限制，其转移的式子如下：

$f_i = \min_{j \in i} f_{i-2^{j-1}} + t_j$

显然，状态转移还有其它条件，整理下来有两条：

1. 要求申请签证时不能在上课。

2. 要求申请签证过程中没有出现过需要检查该护照的课程。

那么我们在转移后将 $f_i$ 处理一下来避免违反第一个条件的情况，使得如果此时如果是在上课时间就一直往后找到第一个不是上课时间的时间点，这个可以用二分找到此时 $f_i$ 所在的课程再预处理解决。但是此时还是不能直接转移。

那么我们们将转移的式子改变一下：

设 $ti$ 为从 $f_{i-2^{j-1}}$ 开始第一个满足第二个条件的时间点。

$f_i = \min_{j \in i} ti + t_j$

目前的问题是求 $ti$，我们发现 $n$ 个课程中间最多只有 $n$ 段空闲时间。

（红色为休息时间）

那么我们对于 $ti$，只需要看 $f_{i-2^{j-1}}$ 到下一个需要用到该护照的课程的时间够不够 $t_j$，不够则往后面一个整块红色一个整块红色地看，看它的左端点到下一个需要用到该护照的课程的时间够不够 $t_j$，找到第一个可行的时间点即可。如果要找到下一个需要用到该护照的课程需要用到二分。

但这么做时间是 $O(n^2 \log n)$ 的，比暴力还劣，需要优化一个 $n$。

我们发现对于每个 $j$ 处理一下 $ti$ 太浪费时间了，不如离线下来在外面处理出每个整块的左端点能够提供的最长时间然后将询问排序后在内部进行 $O(n \log n)$ 离线处理即可，需要使用线段树和离散化。

对于 $P=2$ 的情况也很简单，只需要枚举其中一个护照的集合，另一个护照与其互补即可。关于方案输出，在状态转移过程中记录下转移过程即可。

这样我们得到了一个 $O(n2^n\log n)$ 的大常数做法，被卡常，所以需要进行优化，我简单提一下我优化的点。

1. 由于是单点修改查询前缀最大值，所以可以将线段树换成树状数组。
2. 对于找到不合法 $f_i$ 所在的课程可以不用二分，因为它所在的课程相对 $f_{i-2^{j-1}}$ 一定是递增的，可以打数组记录一下。
3. 使用 C++98。

代码很乱，其实还有一些优化的点，这里就不再赘述了。

code

#include<bits/stdc++.h>
using namespace std;
template<typename G> inline void read(G &x) {x=0;G f=1;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();if(ch=='-') f=-1,ch=getchar();while(ch>='0'&&ch<='9') {x=x*10+(ch^48);ch=getchar();}x*=f;}
const int MAXN=(1<<22)+5;
int d[30];
void update(int x,int z) {
    for(int i=x;i<30;i+=(i&-i)) d[i]=min(d[i],z); 
}
int query(int x) {
    int res=INT_MAX;
    for(int i=x;i;i-=(i&-i)) res=min(res,d[i]);
    return res;
}
void update(int l,int r,int k,int p,int z) {
    if(l==k&&r==k) {
        d[p]=min(d[p],z);
        return;
    }
    int mid=(l+r)>>1;
    if(k<=mid) update(l,mid,k,p<<1,z);
    else update(mid+1,r,k,p<<1|1,z);
    d[p]=min(d[p<<1],d[p<<1|1]);
}
struct node{
    int s,len,t,idx;
}a[30];
int dir[30],bok[30],tmp[30],idx[30];
bool cmp(node x,node y) {
    return x.s<y.s;
}
int n,k,f[MAXN],las[MAXN],as[MAXN],lis[MAXN],ans[30],nxt[30];
bool g[30];
vector<int> v[30];
signed main() {	
    // freopen("passports.in","r",stdin);
    // freopen("passports.out","w",stdout);
    read(n),read(k);
    for(int i=1;i<=n;++i) {
        read(a[i].s),read(a[i].len),read(a[i].t);
        a[i].idx=i;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;++i) dir[i]=a[i].t;
    for(int i=1;i<=n;++i) bok[i]=a[i].s;
    sort(dir+1,dir+1+n);
    int cnt=unique(dir+1,dir+1+n)-dir-1;
    for(int i=1;i<=n;++i) {
        a[i].t=lower_bound(dir+1,dir+1+cnt,a[i].t)-dir;
    }
    for(int i=n;i>=1;--i) {
        if(i==n||a[i].s+a[i].len<a[i+1].s) nxt[i]=a[i].s+a[i].len;
        else nxt[i]=nxt[i+1];
    }
    a[0].len=1,lis[0]=(a[1].s==1);
    f[0]=1;
    for(int i=1;i<(1<<n);++i) f[i]=INT_MAX;
    for(int i=1;i<(1<<n);++i) {
        int ls=0,tot=0;
        for(int j=1;j<=n;++j) {
            if((i>>(j-1))&1) {
                ++tot;
                tmp[tot]=a[j].s;
                idx[tot]=j;
                v[j].clear();
            }
        }
        for(int j=n;j>=1;--j) {
            if((i>>(j-1))&1) {
                int ti=f[i-(1<<(j-1))],p=upper_bound(tmp+1,tmp+1+tot,ti+dir[a[j].t])-tmp-1;
                p=idx[p];
                if(p!=0&&ti<=a[p].s) {
                    v[p].push_back(j);
                    continue;
                }
                if(ti<=a[j].s-dir[a[j].t]-1) {
                    int nw=ti+dir[a[j].t];
                    int k=lis[i-(1<<(j-1))];
                    while(k!=n&&a[k+1].s<=nw) ++k;
                    if(k!=0&&nw<a[k].s+a[k].len) nw=nxt[k];
                    if(nw<f[i]) {
                        f[i]=nw,las[i]=j,as[i]=ti,lis[i]=k;
                    }
                }
            }
        }
        memset(d,127,sizeof(d));
        for(int j=n;j>=1;--j) {
            if((i>>(j-1))&1) {
                for(int t1=0;t1<v[j].size();++t1) {
                    int k=v[j][t1];
                    int ti=query(n-a[k].t+1);
                    if(ti<=a[k].s-dir[a[k].t]-1) {
                        int nw=ti+dir[a[k].t];
                        int p=lis[i-(1<<(j-1))];
                        while(p!=n&&a[p+1].s<=nw) ++p;
                        if(p!=0&&nw<a[p].s+a[p].len) nw=nxt[p];
                        if(nw<f[i]) {
                            f[i]=nw,las[i]=k,as[i]=ti,lis[i]=p;
                        }
                    }
                }
                ls=j;
            }
            if(a[j].s-a[j-1].s-a[j-1].len>0) {
                int k=(ls==0?n:upper_bound(dir+1,dir+1+cnt,a[ls].s-a[j-1].s-a[j-1].len-1)-dir-1);
                if(k!=0) update(n-k+1,a[j-1].s+a[j-1].len);
            }
        }
    }
    if(k==1) {
        for(int i=(1<<n)-1;i<(1<<n);++i) {
            if(f[i]!=INT_MAX&&f[(1<<n)-i-1]!=INT_MAX) {
                puts("YES");
                int nw=i;
                while(nw!=0) {
                    ans[a[las[nw]].idx]=as[nw];
                    g[a[las[nw]].idx]=0;
                    nw-=(1<<(las[nw]-1));
                }
                nw=(1<<n)-i-1;
                while(nw!=0) {
                    ans[a[las[nw]].idx]=as[nw];
                    g[a[las[nw]].idx]=1;
                    nw-=(1<<(las[nw]-1));
                }
                for(int j=1;j<=n;++j) {
                    printf("%d %d\n",g[j]+1,ans[j]);
                }
                return 0;
            }
        }
    }
    else {
        for(int i=0;i<(1<<(n-1));++i) {
            if(f[i]!=INT_MAX&&f[(1<<n)-i-1]!=INT_MAX) {
                puts("YES");
                int nw=i;
                while(nw!=0) {
                    ans[a[las[nw]].idx]=as[nw];
                    g[a[las[nw]].idx]=0;
                    nw-=(1<<(las[nw]-1));
                }
                nw=(1<<n)-i-1;
                while(nw!=0) {
                    ans[a[las[nw]].idx]=as[nw];
                    g[a[las[nw]].idx]=1;
                    nw-=(1<<(las[nw]-1));
                }
                for(int j=1;j<=n;++j) {
                    printf("%d %d\n",g[j]+1,ans[j]);
                }
                return 0;
            }
        }
    }
    puts("NO");
	return 0;
}
/*
2 1
99804934 8385 2669639
99873926 1 2360419

*/