设f[i]是已经走到i号点的值。
先要给第四维离散化、然后去重
第一维排序,第二维cdq分治,第三维cdq分治,第四维树状数组,找到满足j(x,y,z,w)<=i(x,y,z,w)的j,给i统计答案就可以。
然后在做的时候可以直接统计左区间内部答案、统计左区间给右区间造成的答案,但是一定要在这两个做完以后再统计右区间内部的答案,因为用右区间的某个j去更新i时,那个j是会被前面的区间影响的
然后就被卡常了QAQ...分治里一定要写尽量少的sort啊...
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<ctime>
#define LL long long int
#define inf 0x3f3f3f3f
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int maxn=,mod=; LL rd(){
LL x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} struct Node{
int x,y,z,w,i;
LL v;bool b;
}tmp1[maxn],tmp2[maxn],tmp3[maxn],arr1[maxn];
int N,M,mv[maxn],fv[maxn];
LL ma[maxn],fa[maxn];
const int sizN=sizeof(Node); inline void change(int x,LL y,int z){
if(z==){
while(x&&x<=M) ma[x]=mv[x]=,x+=lowbit(x);
return;
}
while(x&&x<=M){
if(ma[x]<y) ma[x]=y,mv[x]=z;
else if(ma[x]==y) mv[x]=(mv[x]+z)%mod;
else break;
x+=lowbit(x);
}
}
inline LL querya(int x){
LL re=;while(x) re=max(re,ma[x]),x-=lowbit(x);return re;
}
inline int queryv(int x){
int re=;LL a=;
while(x){
if(ma[x]>a) re=mv[x],a=ma[x];
else if(ma[x]==a) re=(re+mv[x])%mod;
x-=lowbit(x);
}return re;
} inline bool cmpw(Node a,Node b){return a.w<b.w;}
inline bool cmpz(Node a,Node b){
return a.z==b.z?cmpw(a,b):a.z<b.z;
}
inline bool cmpy(Node a,Node b){
return a.y==b.y?cmpz(a,b):a.y<b.y;
}
inline bool cmpx(Node a,Node b){
return a.x==b.x?cmpy(a,b):a.x<b.x;
} void cdq2(int l,int r){
if(l>=r) return;
//printf("!%d %d\n",l,r);
int m=l+r>>,p=l,q=m+,t=l;
cdq2(l,m);sort(tmp1+l,tmp1+m+,cmpz);
memcpy(tmp3+m+,tmp1+m+,sizN*(r-m));sort(tmp1+m+,tmp1+r+,cmpz);
while(p<=m&&q<=r){
if(tmp1[p].z<=tmp1[q].z){
if(!tmp1[p].b){
change(tmp1[p].w,fa[tmp1[p].i],fv[tmp1[p].i]);
}p++;
}else{
if(tmp1[q].b){
LL a=querya(tmp1[q].w)+tmp1[q].v;int v=queryv(tmp1[q].w);
if(v){
if(a>fa[tmp1[q].i]) fa[tmp1[q].i]=a,fv[tmp1[q].i]=v;
else if(a==fa[tmp1[q].i]) fv[tmp1[q].i]=(fv[tmp1[q].i]+v)%mod;
}
}
q++;
}
}while(q<=r){
if(tmp1[q].b){
LL a=querya(tmp1[q].w)+tmp1[q].v;int v=queryv(tmp1[q].w);
if(v){
if(a>fa[tmp1[q].i]) fa[tmp1[q].i]=a,fv[tmp1[q].i]=v;
else if(a==fa[tmp1[q].i]) fv[tmp1[q].i]=(fv[tmp1[q].i]+v)%mod;
}
}
q++;
}for(int i=l;i<p;i++) change(tmp1[i].w,,);
memcpy(tmp1+m+,tmp3+m+,sizN*(r-m));cdq2(m+,r);
} void cdq1(int l,int r){
if(l>=r) return;
int m=l+r>>,p=l,q=m+,t=l;
cdq1(l,m);sort(arr1+l,arr1+m+,cmpy);
memcpy(tmp2+m+,arr1+m+,sizN*(r-m));sort(arr1+m+,arr1+r+,cmpy);
while(p<=m&&q<=r){
if(arr1[p].y<=arr1[q].y){
tmp1[t]=arr1[p++];tmp1[t].b=;
}else{
tmp1[t]=arr1[q++];tmp1[t].b=;
}t++;
}while(p<=m) tmp1[t]=arr1[p++],tmp1[t++].b=;
while(q<=r) tmp1[t]=arr1[q++],tmp1[t++].b=;
cdq2(l,r);
memcpy(arr1+m+,tmp2+m+,sizN*(r-m));cdq1(m+,r);
} int main(){
//freopen("xzbz.in","r",stdin);
int i,j,k;
N=rd(),M=rd();
for(i=;i<=N;i++){
tmp1[i].i=i;tmp1[i].x=rd();tmp1[i].y=rd();
tmp1[i].z=rd();tmp1[i].w=rd();tmp1[i].v=rd();
}sort(tmp1+,tmp1+N+,cmpw);
for(i=,j=;i<=N;i++){
tmp2[i]=tmp1[i];
if(tmp1[i].w==tmp1[i-].w) tmp2[i].w=j;
else tmp2[i].w=++j;
}M=j;
sort(tmp2+,tmp2+N+,cmpx);
for(i=,j=;i<=N;i++){
if(tmp2[i].x==tmp2[i-].x&&tmp2[i].y==tmp2[i-].y&&tmp2[i].z==tmp2[i-].z&&tmp2[i].w==tmp2[i-].w){
arr1[j].v=(arr1[j].v+tmp2[i].v)%mod;
fa[j]=arr1[j].v;
}else{
arr1[++j]=tmp2[i];arr1[j].i=j;
fa[j]=arr1[j].v;fv[j]=;
}
}N=j;
cdq1(,N);
LL a=;int v=;
for(i=;i<=N;i++){
if(fa[i]>a) a=fa[i],v=fv[i];
else if(fa[i]==a) v=(v+fv[i])%mod;
}printf("%lld\n%d",a,v);
return ;
}