https://mirror.codeforces.com/gym/104813/problem/G

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define vec vector<int>
const int nn=2e5+5;
int n,m,k,timer,fa[nn],sz[nn];
vec id[nn];
vector<pii> tmp[nn],e[nn];
inline int get(pii x,pii y){
	return max(0LL,min(x.se,y.se)-max(y.fi,x.fi)+1LL);
}
inline int getfa(int x){
	if(fa[x]==x) return x;
	return fa[x]=getfa(fa[x]);
}
inline int read(){
	int k=0;
	char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') k=(k<<1)+(k<<3)+(c^48),c=getchar();
	return k;
}
int main(){
	n=read(),m=read(),k=read();
	if(n==1){
		cout<<"YES"<<endl;
		return 0; 
	}
	if(m>k*2+1){
		cout<<"NO"<<endl;
		return 0;
	}
	for(int i=1;i<=m;i++) tmp[i].pb(mp(0,0));
	for(int i=1;i<=k;i++){
		int x1=read(),x2=read(),y=read();
		tmp[y].pb(mp(x1,x2));
	}
	for(int i=1;i<=m;i++){
		tmp[i].pb(mp(n+1,n+1));
		sort(tmp[i].begin(),tmp[i].end());
		for(int j=1;j<tmp[i].size();j++){
			int l=tmp[i][j-1].se+1,r=tmp[i][j].fi-1;
			if(l<=r) e[i].pb(mp(l,r));
		}
		id[i].resize(e[i].size());
	}
	for(int i=1;i<=m;i++){
		for(int j=0;j<e[i].size();j++) id[i][j]=++timer;
	}
	for(int k=1;k<=timer;k++) fa[k]=k,sz[k]=1;
	bool p=true;
	for(int i=1;i<m;i++){
		int k=0,j=0;
		while(k<e[i].size()&&j<e[i+1].size()){
			int len=get(e[i][k],e[i+1][j]);
			if(len>1){
				p=false;
				i=m;
				break;
			}
			if(len==1){
				int fx=getfa(id[i][k]),fy=getfa(id[i+1][j]);
				if(fx!=fy){
					if(sz[fx]>sz[fy]) swap(fx,fy);
					fa[fx]=fy,sz[fy]+=sz[fx];
				}
				if(fx==fy){
					p=false;
					i=m;
					break;
				}
			}
			if(e[i][k].se==e[i+1][j].se) k++,j++;
			else if(e[i][k].se>e[i+1][j].se) j++;
			else k++;
		}
	}
	if(p) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	return 0;
}