1229D - Wojtek and Card Tricks - CodeForces Solution

#include<set>
#include<map>
#include<queue>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#define pr pair
#define f first
#define s second
#define ll long long
#define mp make_pair
#define pll pr<ll,ll>
#define pii pr<int,int>
#define piii pr<int,pii>
using namespace std;
int t[120][5];
int ad[120][120];
int a[200005][5];
int w[200005];
int lp[200005][120];
int d[5];
int us[120],q;
bool ud[5];
bool ap[120];
int lt[120],z;
int calc(int a[])
{
	int rt=24*a[0]+6*a[1]+2*a[2]+a[3];
	for(int i=0;i<1;i++) if(a[i]<a[1]) rt-=6;
	for(int i=0;i<2;i++) if(a[i]<a[2]) rt-=2;
	for(int i=0;i<3;i++) if(a[i]<a[3]) rt-=1;
	return rt;
}
int main()
{
	ios_base::sync_with_stdio(0);
	for(int i=0;i<120;i++)
	{
		t[i][0]=i/24;
		t[i][1]=i%24/6;
		t[i][2]=i%6/2;
		t[i][3]=i%2;
		for(int j=0;j<5;j++) ud[j]=0;
		for(int j=0;j<5;j++)
		{
			int k=t[i][j];
			for(t[i][j]=0;t[i][j]<5;t[i][j]++)
			{
				if(!ud[t[i][j]])
				{
					k--;
					if(k==-1)
					{
						ud[t[i][j]]=1;
						break;
					}
				}
			}
		}
	}
	for(int i=0;i<120;i++)
	{
		for(int j=0;j<120;j++)
		{
			for(int k=0;k<5;k++)
			{
				d[k]=t[i][t[j][k]];
			}
			ad[i][j]=calc(d);
		}
	}
	int n,k;
	cin>>n>>k;
	for(int i=0;i<n;i++) for(int j=0;j<k;j++) cin>>a[i][j],a[i][j]--;
	for(int i=0;i<n;i++) for(int j=k;j<5;j++) a[i][j]=j;
	for(int i=0;i<n;i++) w[i]=calc(a[i]);
	for(int i=0;i<120;i++) lp[n][i]=n+1;
	for(int i=n-1;i>=0;i--)
	{
		for(int j=0;j<120;j++) lp[i][j]=lp[i+1][j];
		lp[i][w[i]]=i;
	}
	ll ans=0;
	ap[0]=1;
	int lc,nc,fr;
	for(int i=0;i<n;i++)
	{
		z=1;
		for(int j=1;j<120;j++) ap[j]=0;
		nc=i;
		q=0;
		while(nc<n)
		{
			lc=nc;
			nc=n;
			fr=0;
			for(int j=0;j<120;j++)
			{
				if(ap[j]) continue;
				if(lp[i][j]<=nc)
				{
					nc=lp[i][j];
					fr=j;
				}
			}
			ans+=(nc-lc)*z;
			us[q++]=fr;
			for(int j=0;j<z;j++)
			{
				for(int k=0;k<q;k++)
				{
					int g=ad[lt[j]][us[k]];
					if(ap[g]) continue;
					lt[z++]=g;
					ap[g]=1;
				}
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}