题目 | 提交记录

struct awa{
	int a,b,c,d,v;
	bool operator <(awa t) const{
		if(a!=t.a) return a<t.a;
		if(b!=t.b) return b<t.b;
		if(c!=t.c) return c<t.c;
		if(d!=t.d) return d<t.d;
		return v<t.v;
	}
}a[N];
bool cmp(pair<awa,int> x,pair<awa,int> y){
	return x.first.b<y.first.b;
}
bool cmp1(pair<awa,int> x,pair<awa,int> y){
	return x.first.c<y.first.c;
}
bool cmp2(pair<awa,int> x,pair<awa,int> y){
	return x.first.d<y.first.d;
}
int n,m;
long long f[N],g[N],f_[N>>3][256],g_[N>>3][256];
unsigned int h[2048][M],h1[2048][M],h2[2048][M];
pair<awa,int> b[N],b1[N],b2[N];
signed main(){
	//	for(int i=1;i<256;i+=2) g_[0][i]=1;
	std::ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	//	if(n>50000) return 0;
	for(int i=1;i<=n;++i) cin >> a[i].a >> a[i].b >> a[i].c >> a[i].d >> a[i].v;
	sort(a+1,a+1+n);
	for(int i=1;i<=n;++i) b[i]=b1[i]=b2[i]=pair<awa,int>(a[i],i);
	sort(b+1,b+1+n,cmp);
	sort(b1+1,b1+1+n,cmp1);
	sort(b2+1,b2+1+n,cmp2);
	//	for(int i=1;i<=n;++i) cout << i << ": " << a[i].a << " " << a[i].b << " " << a[i].c << " " << a[i].d << " " << a[i].v << endl;
	g[0]=1;
	for(int k=0;k<=(n>>11);++k){
		for(int j=1;j<=n>>5;++j) h[0][j]=h1[0][j]=h2[0][j]=0;
		for(int i=1,j=0,lp=0;i<=n;++i){
			int p=b[i].second;
			if(p>=(k<<11) && p<(k+1<<11)){
				p&=2047;
				memmove(h[p],h[lp],sizeof(h[0]));
				for(;j<=n && b[j].first.b<=b[i].first.b;++j){
					/*if(b[i].first.b>=b[j].first.b)*/ h[p][b[j].second>>5]|=1u<<(b[j].second&31);
					//					cout << "1: " << b[j].second << " " << (p|(k<<12)) << endl;
				}
				lp=p;
			}
		}
		for(int i=1,j=0,lp=0;i<=n;++i){
			int p=b1[i].second;
			if(p>=(k<<11) && p<(k+1<<11)){
				p&=2047;
				memmove(h1[p],h1[lp],sizeof(h1[0]));
				for(;j<=n && b1[j].first.c<=b1[i].first.c;++j){
					/*if(b1[i].first.c>=b1[j].first.c)*/ h1[p][b1[j].second>>5]|=1u<<(b1[j].second&31);
					//					cout << "2: " << b1[j].second << " " << (p|(k<<12)) << endl;
				}
				lp=p;
			}
		}
		for(int i=1,j=0,lp=0;i<=n;++i){
			int p=b2[i].second;
			if(p>=(k<<11) && p<(k+1<<11)){
				p&=2047;
				memmove(h2[p],h2[lp],sizeof(h2[0]));
				for(;j<=n && b2[j].first.d<=b2[i].first.d;++j){
					h2[p][b2[j].second>>5]|=1u<<(b2[j].second&31);
				}
				lp=p;
			}
		}
		for(int i=0;i<=2047;++i){
			for(int j=0;j<=n>>5;++j) h[i][j]&=h1[i][j]&h2[i][j];
			//			cout << h[i][0] << endl;
			h[i][(k<<6)|(i>>5)]&=0xffffffff^(1<<(i&31));
		}
		//		cout << g[0] << endl;
		//		cout << g[0] << endl;
		//		cout << g[0] << endl;
		//		cout << g[0] << endl;
		//		cout << g[0] << endl;
		for(int i=(k<<11),ii=0;i<(k+1<<11);++i,++ii){
//			if(i>=72000) return 0;
			//			cout << g[0] << endl;
			//			cout << g[0] << endl;
			//			cout << g[0] << endl;
			//			cout << g[0] << endl;
			//			cout << g[0] << endl;
			int t;
			long long* ff,*gg;
			for(int j=0;j<i;j+=32){
				t=h[ii][j>>5],ff=f_[j>>3],gg=g_[j>>3];
				if(ff[(t>>0)&255|0]>=f[i]) {
					if(ff[(t>>0)&255|0]>f[i]) f[i]=ff[(t>>0)&255|0],g[i]=gg[(t>>0)&255|0];
					else g[i]+=gg[(t>>0)&255|0];
				}
				if(ff[(t>>8)&255|256]>=f[i]) {
					if(ff[(t>>8)&255|256]>f[i]) f[i]=ff[(t>>8)&255|256],g[i]=gg[(t>>8)&255|256];
					else g[i]+=gg[(t>>8)&255|256];
				}
				if(ff[(t>>16)&255|512]>=f[i]) {
					if(ff[(t>>16)&255|512]>f[i]) f[i]=ff[(t>>16)&255|512],g[i]=gg[(t>>16)&255|512];
					else g[i]+=gg[(t>>16)&255|512];
				}
				if(ff[(t>>24)&255|768]>=f[i]) {
					if(ff[(t>>24)&255|768]>f[i]) f[i]=ff[(t>>24)&255|768],g[i]=gg[(t>>24)&255|768];
					else g[i]+=gg[(t>>24)&255|768];
				}
//				if(ff[(t>>8)&255|256]>=f[i]) f[i]=ff[(t>>8)&255|256];
//				if(ff[(t>>16)&255|512]>=f[i]) f[i]=ff[(t>>16)&255|512];
//				if(ff[(t>>24)&255|768]>=f[i]) f[i]=ff[(t>>24)&255|768];
				
				
				
				/*
				  if((j<i)&(h[ii][t]>>0)&(f[j|0]>f[i])&1) f[i]=f[j|0];
				  if((j<i)&(h[ii][t]>>1)&(f[j|1]>f[i])&1) f[i]=f[j|1];
				  if((j<i)&(h[ii][t]>>2)&(f[j|2]>f[i])&1) f[i]=f[j|2];
				  if((j<i)&(h[ii][t]>>3)&(f[j|3]>f[i])&1) f[i]=f[j|3];
				  if((j<i)&(h[ii][t]>>4)&(f[j|4]>f[i])&1) f[i]=f[j|4];
				  if((j<i)&(h[ii][t]>>5)&(f[j|5]>f[i])&1) f[i]=f[j|5];
				  if((j<i)&(h[ii][t]>>6)&(f[j|6]>f[i])&1) f[i]=f[j|6];
				  if((j<i)&(h[ii][t]>>7)&(f[j|7]>f[i])&1) f[i]=f[j|7];
				  if((j<i)&(h[ii][t]>>8)&(f[j|8]>f[i])&1) f[i]=f[j|8];
				  if((j<i)&(h[ii][t]>>9)&(f[j|9]>f[i])&1) f[i]=f[j|9];
				  if((j<i)&(h[ii][t]>>10)&(f[j|10]>f[i])&1) f[i]=f[j|10];
				  if((j<i)&(h[ii][t]>>11)&(f[j|11]>f[i])&1) f[i]=f[j|11];
				  if((j<i)&(h[ii][t]>>12)&(f[j|12]>f[i])&1) f[i]=f[j|12];
				  if((j<i)&(h[ii][t]>>13)&(f[j|13]>f[i])&1) f[i]=f[j|13];
				  if((j<i)&(h[ii][t]>>14)&(f[j|14]>f[i])&1) f[i]=f[j|14];
				  if((j<i)&(h[ii][t]>>15)&(f[j|15]>f[i])&1) f[i]=f[j|15];
				  if((j<i)&(h[ii][t]>>16)&(f[j|16]>f[i])&1) f[i]=f[j|16];
				  if((j<i)&(h[ii][t]>>17)&(f[j|17]>f[i])&1) f[i]=f[j|17];
				  if((j<i)&(h[ii][t]>>18)&(f[j|18]>f[i])&1) f[i]=f[j|18];
				  if((j<i)&(h[ii][t]>>19)&(f[j|19]>f[i])&1) f[i]=f[j|19];
				  if((j<i)&(h[ii][t]>>20)&(f[j|20]>f[i])&1) f[i]=f[j|20];
				  if((j<i)&(h[ii][t]>>21)&(f[j|21]>f[i])&1) f[i]=f[j|21];
				  if((j<i)&(h[ii][t]>>22)&(f[j|22]>f[i])&1) f[i]=f[j|22];
				  if((j<i)&(h[ii][t]>>23)&(f[j|23]>f[i])&1) f[i]=f[j|23];
				  if((j<i)&(h[ii][t]>>24)&(f[j|24]>f[i])&1) f[i]=f[j|24];
				  if((j<i)&(h[ii][t]>>25)&(f[j|25]>f[i])&1) f[i]=f[j|25];
				  if((j<i)&(h[ii][t]>>26)&(f[j|26]>f[i])&1) f[i]=f[j|26];
				  if((j<i)&(h[ii][t]>>27)&(f[j|27]>f[i])&1) f[i]=f[j|27];
				  if((j<i)&(h[ii][t]>>28)&(f[j|28]>f[i])&1) f[i]=f[j|28];
				  if((j<i)&(h[ii][t]>>29)&(f[j|29]>f[i])&1) f[i]=f[j|29];
				  if((j<i)&(h[ii][t]>>30)&(f[j|30]>f[i])&1) f[i]=f[j|30];
				  if((j<i)&(h[ii][t]>>31)&(f[j|31]>f[i])&1) f[i]=f[j|31];
				 */
				
				//				if((h[ii][j>>5]>>(j&31))&(f[j]>f[i])&1) f[i]=f[j];
			}
//			for(int j=0;j<i;j+=32){
//				t=h[ii][j>>5],ff=f_[j>>3],gg=g_[j>>3];
//				if(ff[(t>>0)&255|0]==f[i]) g[i]+=gg[(t>>0)&255|0];
//				//				if(i<=20) cout << i << " " << g[i] << endl;
//				if(ff[(t>>8)&255|256]==f[i]) g[i]+=gg[(t>>8)&255|256];
//				if(ff[(t>>16)&255|512]==f[i]) g[i]+=gg[(t>>16)&255|512];
//				if(ff[(t>>24)&255|768]==f[i]) g[i]+=gg[(t>>24)&255|768];
//				
//			}
			f[i]+=a[i].v;
			g[i]%=p;
			//			if(i<=n) cout << i << " " << f[i] << " " << g[i] << endl;
			//			cout << g[0] << endl;
			for(int j=0;j<=255;++j){
				if((j>>(i&7))&1){
					if(f[i]>f_[i>>3][j]) f_[i>>3][j]=f[i],g_[i>>3][j]=0;
				}
			}
			for(int j=0;j<=255;++j){
				if((j>>(i&7))&1 && f[i]==f_[i>>3][j]) g_[i>>3][j]+=g[i];
			}
		}
	}
	long long ans=*max_element(f+1,f+1+n);
	long long ans2=0;
	for(int i=1;i<=n;++i){
		if(f[i]==ans) ans2+=g[i];
	}
	cout << ans << endl << ans2%p << endl;
	return 0;