WA 样例没过求助
查看原帖
WA 样例没过求助
556362
Unnamed114514楼主2022/12/17 11:15
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+5,inf=1e9,maxk=4e6+5;
int cnt,n,ans,bef,num,a[maxn],b[maxn],c[maxn],d[maxn],y[maxn<<1],V[maxn<<1];
map<int,int> M;
inline int read(){
	int res=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		f|=(ch=='-');
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		res=(res<<1)+(res<<3)+(ch^'0');
		ch=getchar();
	}
	return f?-res:res;
}
struct ask{
	int p,l,r,v;
	inline bool operator <(const ask &o) const{
		return p<o.p||(p==o.p&&v<o.v);
	}
}N[maxn<<1];
struct ST{
	int l,r,ls,rs,sum,tag;
}t[maxk];
inline void pushdown(int p,int l,int r){
	int mid=l+r>>1;
	if(!t[p].ls)
		t[p].ls=++num,t[t[p].ls].l=l,t[t[p].ls].r=mid;
	if(!t[p].rs)
		t[p].rs=++num,t[t[p].rs].l=mid+1,t[t[p].rs].r=r;
	t[t[p].ls].sum=t[p].tag*(t[t[p].ls].r-t[t[p].ls].l+1);
	t[t[p].ls].tag=t[p].tag;
	t[t[p].rs].sum=t[p].tag*(t[t[p].rs].r-t[t[p].rs].l+1);
	t[t[p].rs].tag=t[p].tag;
}
void Cover(int p,int l,int r,int v){
	if(l<=t[p].l&&t[p].r<=r){
		t[p].sum=v*(t[p].r-t[p].l+1);
		t[p].tag=v;
		return;
	}
	pushdown(p,t[p].l,t[p].r);
	if(l<=t[t[p].ls].r)
		Cover(t[p].ls,l,r,v);
	if(t[t[p].rs].l<=r)
		Cover(t[p].rs,l,r,v);
	t[p].sum=t[t[p].ls].sum+t[t[p].rs].sum;
}
signed main(){
	n=read();
	for(int i=1;i<=n;++i)
		a[i]=read(),b[i]=read(),c[i]=read(),d[i]=read(),y[i]=b[i],y[i+n]=d[i];
	sort(y+1,y+2*n+1);
	int tot=unique(y+1,y+2*n+1)-y;
	for(int i=1;i<=tot;++i)
		V[i]=y[i],M[y[i]]=i;
	for(int i=1;i<=n;++i)
		N[i]=ask({M[b[i]],a[i],c[i],1}),N[i+n]=ask({M[d[i]]+1,a[i],c[i],0});
	sort(N+1,N+2*n+1);
	cnt=1;
	num=1,t[1].l=1,t[1].r=inf;
	for(int i=1;i<=2*n;++i){
		while(N[cnt].p==i){
			Cover(1,N[cnt].l,N[cnt].r,N[cnt].v);
			++cnt;
		}
		ans+=t[1].sum*(V[i]-V[i-1]);
		puts("");
	}
	printf("%lld\n",ans);
	return 0;
}
2022/12/17 11:15
加载中...