878D - Magic Breeding - CodeForces Solution

#include<bits/stdc++.h>
#define rg register
#define file(x)freopen(x".in","r",stdin);freopen(x".out","w",stdout)

using namespace std;

const int maxn=1e5+10;
const int maxK=12+1;

int n,K,Q;
int A[maxn][maxK];
int Rk[maxK][maxn];
int Value[maxK][maxn*maxK];

int Stand[maxn*maxK];

bitset<(1<<12)> Sta[maxn<<1];
inline int Query(int x,int Column)
{
	Column=Stand[Column];
	return Sta[x][Column];
}

int main()
{
	scanf("%d %d %d",&n,&K,&Q);
	for(rg int i=1;i<=K;i+=1)
		for(rg int j=1;j<=n;j+=1)
			scanf("%d",A[j]+i);
	for(rg int i=1;i<=n;i+=1)
	{
		static int P[maxK];
		for(rg int j=1;j<=K;j+=1)P[j]=j;
		sort(P+1,P+K+1,[&](auto x,auto y){return A[i][x]<A[i][y];});
		for(rg int j=1;j<=K;j+=1)Rk[P[j]][i]=j;
		sort(A[i]+1,A[i]+K+1);
	}
	for(rg int i=1;i<=K;i+=1)
	{
		int id=0;
		for(rg int j=1;j<=n;j+=1)
		{
			for(rg int k=1;k<=Rk[i][j];k+=1)Value[i][++id]=1;
			for(rg int k=Rk[i][j]+1;k<=K;k+=1)Value[i][++id]=0;
		}
	}
	for(rg int i=1;i<=n*K;i+=1)
	{
		int &p=Stand[i];
		p=0;
		for(rg int j=K;j;j-=1)
		{
			p<<=1;
			p+=Value[j][i];
		}
	}
	for(rg int i=0;i<(1<<K);i+=1)
		for(rg int j=1;j<=K;j+=1)
			Sta[j][i]=(i>>(j-1))&1;
	int tnt=K;
	while(Q--)
	{
		int opt,x,y;scanf("%d %d %d",&opt,&x,&y);
		if(opt==1)Sta[++tnt]=Sta[x]|Sta[y];
		else if(opt==2)Sta[++tnt]=Sta[x]&Sta[y];
		else
		{
			int Be=(y-1)*K+1,End=y*K;
			int pos=Be;
			while(pos<End&&Query(x,pos+1))pos+=1;
			pos=pos-Be+1;
			printf("%d\n",A[y][pos]);
		}
	}
	return 0;
}
//ggggg