#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define file(x) freopen(x ".in","r",stdin),freopen(x ".out","w",stdout);
#define maxn 200005
#define maxl
#define mod
using namespace std;
int c,T,n,tot,rt;
#define getc (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)
char cb[1<<15],*cs,*ct;
inline void read(auto &num){
char ch;int f=1;
while(!isdigit(ch=getc))if(ch=='-')f=-1;
for(num=ch-'0';isdigit(ch=getc);num=num*10+ch-'0');
num*=f;
}
struct que{
int a,b,num;
ll t;
}a[maxn];
ll now;
struct node{int l,r,cnt,tag;ll sum;}tr[20000000];
inline void push_up(int p){
tr[p].cnt=tr[tr[p].l].cnt+tr[tr[p].r].cnt;
tr[p].sum=tr[tr[p].l].sum+tr[tr[p].r].sum;
}
inline void addsum(int &p,int l,int r,int x){
if(!p)p=++tot;
if(l==r){tr[p].cnt=1,tr[p].sum=l;return;}
int mid=(l+r)>>1;
if(x<=mid)addsum(tr[p].l,l,mid,x);
if(x>mid)addsum(tr[p].r,mid+1,r,x);
push_up(p);
}
inline void f(int &p,int l,int r,int k){
if(!p)p=++tot;
if(k==1)tr[p].cnt=r-l+1,tr[p].sum=1ll*(l+r)*(r-l+1)/2;
if(k==2)tr[p].cnt=tr[p].sum=0;
if(l!=r)tr[p].tag=k;
}
inline void push_down(int p,int l,int r){
if(!tr[p].tag||l==r)return;
int mid=(l+r)>>1;
f(tr[p].l,l,mid,tr[p].tag);
f(tr[p].r,mid+1,r,tr[p].tag);
tr[p].tag=0;
}
inline int getpos(int p,int l,int r,int rk){
if(l==r)return l;
push_down(p,l,r);
int mid=(l+r)>>1;
if(rk<=tr[tr[p].l].cnt)return getpos(tr[p].l,l,mid,rk);
return getpos(tr[p].r,mid+1,r,rk-tr[tr[p].l].cnt);
}
inline int getpos2(int p,int l,int r,int frm,int rk,int lft){
if(l==r)return l;
push_down(p,l,r);
int mid=(l+r)>>1;
if(frm>mid)return getpos2(tr[p].r,mid+1,r,frm,rk,lft-tr[tr[p].l].cnt);
if(rk<=(mid-frm+1)-(tr[tr[p].l].cnt-lft))return getpos2(tr[p].l,l,mid,frm,rk,lft);
else return getpos2(tr[p].r,mid+1,r,mid+1,rk-((mid-frm+1)-(tr[tr[p].l].cnt-lft)),0);
}
inline int getpos3(int p,int l,int r,int frm,int rk,int rit){
if(l==r)return l;
push_down(p,l,r);
int mid=(l+r)>>1;
if(frm<=mid)return getpos3(tr[p].l,l,mid,frm,rk,rit-tr[tr[p].r].cnt);
if(rk<=(frm-mid)-(tr[tr[p].r].cnt-rit))return getpos3(tr[p].r,mid+1,r,frm,rk,rit);
else return getpos3(tr[p].l,l,mid,mid,rk-((frm-mid)-(tr[tr[p].r].cnt-rit)),0);
}
inline int getsum(int p,int l,int r,int L,int R){
if(!p)return 0;
if(L<=l&&r<=R)return tr[p].cnt;
push_down(p,l,r);
int mid=(l+r)>>1,res=0;
if(L<=mid)res+=getsum(tr[p].l,l,mid,L,R);
if(R>mid)res+=getsum(tr[p].r,mid+1,r,L,R);
return res;
}
inline ll getsum2(int p,int l,int r,int L,int R){
if(!p)return 0;
if(L<=l&&r<=R)return tr[p].sum;
push_down(p,l,r);
int mid=(l+r)>>1;
ll res=0;
if(L<=mid)res+=getsum2(tr[p].l,l,mid,L,R);
if(R>mid)res+=getsum2(tr[p].r,mid+1,r,L,R);
return res;
}
inline void addsum(int &p,int l,int r,int L,int R,int k){
if(!p)p=++tot;
if(L<=l&&r<=R){f(p,l,r,k);return;}
push_down(p,l,r);
int mid=(l+r)>>1;
if(L<=mid)addsum(tr[p].l,l,mid,L,R,k);
if(R>mid)addsum(tr[p].r,mid+1,r,L,R,k);
push_up(p);
}
int main(){
file("move")
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
read(c),read(T);
while(T--){
now=tot=rt=0;
read(n);
for(int i=1;i<=n;i++)read(a[i].a),read(a[i].b),read(a[i].t),addsum(rt,1,1e9,a[i].a),a[i].num=i;
sort(a+1,a+n+1,[](que x,que y){return x.t<y.t;});
bool ans=1;
for(int i=1;i<=n;i++){
if(now>a[i].t){ans=0;break;}
int pos=getpos(rt,1,1e9,a[i].num);
if(pos==a[i].b)continue;
if(pos<a[i].b){
int has=getsum(rt,1,1e9,pos,a[i].b-1);
int lft=getsum(rt,1,1e9,1,a[i].b-1);
int pos2=getpos2(rt,1,1e9,a[i].b,has,lft);
ll needt=1ll*(a[i].b+pos2)*(pos2-a[i].b+1)/2-getsum2(rt,1,1e9,pos,pos2);
if(now+needt>a[i].t){ans=0;break;}
now+=needt;
addsum(rt,1,1e9,a[i].b,pos2,1);
addsum(rt,1,1e9,pos,a[i].b-1,2);
}else{
int has=getsum(rt,1,1e9,a[i].b+1,pos);
int rit=getsum(rt,1,1e9,a[i].b+1,1e9);
int pos3=getpos3(rt,1,1e9,a[i].b,has,rit);
ll needt=getsum2(rt,1,1e9,pos3,pos)-1ll*(pos3+a[i].b)*(a[i].b-pos3+1)/2;
if(now+needt>a[i].t){ans=0;break;}
now+=needt;
addsum(rt,1,1e9,pos3,a[i].b,1);
addsum(rt,1,1e9,a[i].b+1,pos,2);
}
}
if(ans)cout<<"Yes\n";
else cout<<"No\n";
memset(tr,0,(tot+1)*sizeof tr[0]);
}
}
linjingxiang LV 2
京公网安备 11011102002149号