1606D - Red-Blue Matrix - CodeForces Solution

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <cctype>
#include <vector>
#include <queue>
#include <bitset>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using namespace std;
typedef long long ll;
typedef pair <int, int> Pii;
const int INF=0x3f3f3f3f;
const int cp=998244353;
inline int mod(int x){if(x>=cp) x-=cp;if(x<0) x+=cp;return x;}
inline void plust(int &x, int y){x=mod(x+y);return ;}
inline void minut(int &x, int y){x=mod(x-y);return ;}
inline int read(){
	char ch=getchar();int x=0, f=1;
	while(!isdigit(ch)){if(ch=='-') f=-1; ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x*f;
}
inline void write(int x){
    if(x<0) putchar('-'), x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline int ksm(int a, int b=cp-2){
	int ret=1;
	for(; b; b>>=1, a=1ll*a*a%cp)
		if(b&1) ret=1ll*ret*a%cp;
	return ret;
}
const int N=5e5+5;
int n, m, id[N];
vi a[N], lmx[N], rmx[N], lmn[N], rmn[N];
char ans[N];
bool cmp(int x, int y){return a[x][1]<a[y][1];}
bool check(int x, int y){return lmx[x][y]<lmn[x+1][y]&&rmn[x][y+1]>rmx[x+1][y+1];}
void solve(){
	n=read(), m=read();
	for(int i=1; i<=n; ++i){
		a[i].resize(m+1);
		lmx[i].resize(m+1, 0), rmx[i].resize(m+1, 0);
		lmn[i].resize(m+1, -INF), rmn[i].resize(m+1, -INF);
		id[i]=i;
		for(int j=1; j<=m; ++j)
			a[i][j]=read();
	}
	sort(id+1, id+n+1, cmp);
	for(int i=1; i<=n; ++i)
		for(int j=1; j<=m; ++j)
			lmx[i][j]=rmx[i][j]=lmn[i][j]=rmn[i][j]=a[id[i]][j];
	for(int i=2; i<=n; ++i)
		lmx[i][1]=max(lmx[i][1], lmx[i-1][1]), 
		rmn[i][m]=min(rmn[i][m], rmn[i-1][m]);
	for(int i=n; i>=2; --i)
		lmn[i-1][1]=min(lmn[i][1], lmn[i-1][1]),
		rmx[i-1][m]=max(rmx[i][m], rmx[i-1][m]);
	for(int i=2; i<=m; ++i) 
		lmx[1][i]=max(lmx[1][i], lmx[1][i-1]),
		lmn[n][i]=min(lmn[n][i], lmn[n][i-1]);
	for(int i=m; i>=2; --i)
		rmn[1][i-1]=min(rmn[1][i-1], rmn[1][i]),
		rmx[n][i-1]=max(rmx[n][i-1], rmx[n][i]);
	for(int i=2; i<=n; ++i){
		for(int j=2; j<=m; ++j) 
			lmx[i][j]=max(lmx[i][j], max(lmx[i][j-1], lmx[i-1][j]));
		for(int j=m-1; j>=1; --j) 
			rmn[i][j]=min(rmn[i][j], min(rmn[i][j+1], rmn[i-1][j]));
	}
	for(int i=n-1; i>=1; --i){
		for(int j=2; j<=m; ++j)
			lmn[i][j]=min(lmn[i][j], min(lmn[i][j-1], lmn[i+1][j]));
		for(int j=m-1; j>=1; --j)
			rmx[i][j]=max(rmx[i][j], max(rmx[i][j+1], rmx[i+1][j]));
	}
	// for(int i=1; i<=n; ++i) printf("%d ", id[i]);puts("");
	// printf("-----------------\n");
	// for(int i=1; i<=n; ++i, puts(""))
		// for(int j=1; j<=m; ++j)
			// printf("%d ", lmx[i][j]);
	// printf("-----------------\n");
	// for(int i=1; i<=n; ++i, puts(""))
		// for(int j=1; j<=m; ++j)
			// printf("%d ", rmn[i][j]);
	// printf("-----------------\n");
	// for(int i=1; i<=n; ++i, puts(""))
		// for(int j=1; j<=m; ++j)
			// printf("%d ", lmn[i][j]);
	// printf("-----------------\n");
	// for(int i=1; i<=n; ++i, puts(""))
		// for(int j=1; j<=m; ++j)
			// printf("%d ", rmx[i][j]);
	// printf("-----------------\n");
	int ansx=0, ansy=0;
	// if(3<n) printf("----------->%d [%d<%d] [%d>%d]\n", check(3, 1), lmx[3][1], lmn[4][1], rmn[3][2], rmx[4][2]);
	for(int i=1; i<n; ++i)
		for(int j=1; j<m; ++j)
			if(check(i, j)){ansx=i, ansy=j;break;}
	if(ansx&&ansy){
		puts("YES");
		for(int i=1; i<=ansx; ++i) ans[id[i]]='B';
		for(int i=ansx+1; i<=n; ++i) ans[id[i]]='R';
		for(int i=1; i<=n; ++i) putchar(ans[i]);printf(" %d\n", ansy);
	}
	else puts("NO");
	for(int i=1; i<=n; ++i) 
		vi ().swap(a[i]),
		vi ().swap(lmx[i]), vi ().swap(rmx[i]),
		vi ().swap(lmn[i]), vi ().swap(rmn[i]);
}
signed main(){
	int T=read();while(T--) solve();
	return 0;
}