Submission #3421701

---

Source Code Expand

#include<algorithm>
#include<cstring>
#include<cctype>
#include<cstdio>
#include<vector>
#define rep(i,x,y) for(int i=x; i<=y; ++i)
#define repd(i,x,y) for(int i=x; i>=y; --i)
#define pb push_back
 
using namespace std;
const int N=305,M=4510005,mod=1000000007;
int n,m,id[N][N][N],tp,f[2][M],vis[M],nw,tot,ans;
struct data{int l,x;};
vector <data> vt[N];
 
int getint()
{
	char ch;
	while(!isdigit(ch=getchar()));
	int x=ch-48;
	while(isdigit(ch=getchar())) x=x*10+ch-48;
	return x;
}
 
void inc(int x,int y)
{
	if(vis[x]!=nw) f[tp][x]=0,vis[x]=nw;
	f[tp][x]=(f[tp][x]+y)%mod;
}
 
int main()
{
	n=getint(),m=getint();
	rep(i,1,m)
	{
		int l=getint(),r=getint(),x=getint();
		vt[r].pb((data){l,x});
	}
	memset(vis,-1,sizeof(vis));
	rep(i,0,n) rep(j,0,max(0,i-1)) rep(k,0,max(0,j-1)) id[i][j][k]=++tot;
	f[0][id[0][0][0]]=1,vis[id[0][0][0]]=0;
	rep(i,1,n)
	{
		tp^=1,nw=i;
		rep(x,i-1,i-1)
			rep(y,0,max(0,x-1))
				rep(z,0,max(0,y-1))
					if(vis[id[x][y][z]]==i-1)
					{
						int tmp=f[tp^1][id[x][y][z]];
						inc(id[i][y][z],tmp);
						inc(id[i][x][z],tmp);
						inc(id[i][x][y],tmp);
					}
		rep(x,i,i)
			rep(y,0,max(0,x-1))
				rep(z,0,max(0,y-1))
				{
					int sz=vt[i].size();
					bool jdg=0;
					rep(j,0,sz-1)
					{
						int l=vt[i][j].l;
						int t=(x>=l)+(y>=l)+(z>=l);
						if(t!=vt[i][j].x) {jdg=1; break;}
					}
					if(jdg) vis[id[x][y][z]]=-1;
				}
	}
	rep(i,1,tot) if(vis[i]==n) ans=(ans+f[tp][i])%mod;
	printf("%d\n",ans);			
	return 0;
}

Submission Info

Judge Result