【悬赏关注】萌新四维偏序模板25分其余WA求助
查看原帖
【悬赏关注】萌新四维偏序模板25分其余WA求助
743811
Shakespeare07楼主2023/2/18 15:24

rt.

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){
	int s=0,w=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-') w=-1;
		c=getchar();
	}
	while(isdigit(c)){
		s=(s<<3)+(s<<1)+(c^48);
		c=getchar();
	}
	return s*w;
}
const int N=1e5+5;
int n;
struct node{
	int x,y,z,w,id,val,mx,opt;
	bool operator == (const node &p){
		return x==p.x && y==p.y && z==p.z && w==p.w;
	}
}a[N],tmp[N];
int b[N],tot;
bool cmp1(node x,node y){
	if(x.x!=y.x) return x.x<y.x;
	if(x.y!=y.y) return x.y<y.y;
	if(x.z!=y.z) return x.z<y.z;
	return x.w<y.w;
}
bool cmp2(node x,node y){
	if(x.y!=y.y) return x.y<y.y;
	if(x.z!=y.z) return x.z<y.z;
	return x.w<y.w;
}
bool cmp3(node x,node y){
	if(x.z!=y.z) return x.z<y.z;
	return x.w<y.w;
}
int c[N];
void add(int x,int y){
	for(;x<N;x+=x&-x) c[x]=max(c[x],y);
}
void clr(int x){
	for(;x<N;x+=x&-x) c[x]=0;
}
int ask(int x){
	int res=-2e9;
	for(;x;x-=x&-x) res=max(res,c[x]);
	return res;
}
int cnt;
int pos1[N],pos2[N];
void cdq2(int l,int r){
	if(l==r) return;
	int mid=l+r>>1;
	cdq2(l,mid);
	sort(a+l,a+mid+1,cmp3);
	sort(a+mid+1,a+r+1,cmp3);
	int j=l;
	for(int i=mid+1;i<=r;++i){
		while(j<=mid && a[j].z<=a[i].z){
			if(a[j].opt) add(a[j].w,a[j].mx);
			++j;
		}
		if(!a[i].opt) a[i].mx=max(a[i].mx,ask(a[i].w)+a[i].val);
	}
	for(int i=l;i<j;++i) if(a[i].opt) clr(a[j].w);
	for(int i=l;i<=r;++i) tmp[pos2[a[i].id]]=a[i];
	for(int i=l;i<=r;++i) a[i]=tmp[i];
	cdq2(mid+1,r);
}
void cdq1(int l,int r){
	if(l==r) return;
	int mid=l+r>>1;
	cdq1(l,mid);
	for(int i=l;i<=mid;++i) a[i].opt=1;
	for(int i=mid+1;i<=r;++i) a[i].opt=0;
	sort(a+l,a+r+1,cmp2);
	for(int i=l;i<=r;++i){
		pos2[a[i].id]=i;
	}
	cdq2(l,r);
	for(int i=l;i<=r;++i) tmp[pos1[a[i].id]]=a[i];
	for(int i=l;i<=r;++i) a[i]=tmp[i];
	cdq1(mid+1,r);
}
signed main(){
	n=read();
	for(int i=1;i<=n;++i){
		int x=read(),y=read(),z=read(),w=read(),val=read();
		a[i].x=x,a[i].y=y,a[i].z=z,a[i].w=w;
		a[i].val=val;
		b[i]=a[i].w;
	}
	sort(b+1,b+n+1);
	tot=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;++i) a[i].w=lower_bound(b+1,b+tot+1,a[i].w)-b;
	sort(a+1,a+n+1,cmp1);
	for(int i=1;i<=n;++i){
		if(a[i]==a[i-1]){
			a[cnt].val+=max(0LL,a[i].val);
		}
		else{
			a[++cnt]=a[i];
		}
	}
	for(int i=1;i<=cnt;++i){
		a[i].id=i;
		a[i].mx=a[i].val;
		pos1[a[i].id]=i;
	}
	cdq1(1,cnt);
	int ans=-2e9;
	for(int i=1;i<=cnt;++i){
		ans=max(ans,a[i].mx);
	}
	printf("%lld\n",ans);
	return 0;
}
2023/2/18 15:24
加载中...