TLE #3~#11求助
查看原帖
TLE #3~#11求助
551917
110821zj_hhx楼主2024/12/21 18:41
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#define int long long
using namespace std;
int n,t,trm[1600005],cnt,mxk;
int x_1[200005],x_2[200005],y_1[200005],y_2[200005],q[1600005],trl[1600005],mp2[200005]; 
map<int,int>mp1;
struct edge{
	int x,y_1,y_2;
	int val;
}e[200005];
void build(int k,int l,int r){
	mxk=max(mxk,k);
	if(l+1==r) return;
	int mid=(l+r)/2;
	build(k*2,l,mid);
	build(k*2+1,mid,r);
}
void update(int k,int l,int r,int x,int y,int v){
	if(k>mxk) return;
	if(x<=l&&r<=y){
		trm[k]+=v;
	}else{
		int mid=(l+r)/2;
		if(l<mid) update(k*2,l,mid,x,y,v);
		if(mid<r) update(k*2+1,mid,r,x,y,v);
	}
	if(trm[k]>0) trl[k]=mp2[r]-mp2[l];
	else trl[k]=trl[k*2]+trl[k*2+1];
}
bool cmp(edge x,edge y){
    return x.x<y.x;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x_1[i]>>y_1[i]>>x_2[i]>>y_2[i];
		e[i]=(edge){x_1[i],y_1[i],y_2[i],1};
		e[i+n]=(edge){x_2[i],y_1[i],y_2[i],-1};
		mp2[i]=y_1[i],mp2[i+n]=y_2[i];
	}
	n*=2;
	sort(mp2+1,mp2+n+1);
	cnt=unique(mp2+1,mp2+n+1)-mp2-1;
	for(int i=1;i<=cnt;i++) mp1[mp2[i]]=i;
	sort(e+1,e+n+1,cmp);
	build(1,1,cnt);
	int ans=0;
	for(int i=1;i<=n;i++){
		update(1,1,cnt,mp1[e[i].y_1],mp1[e[i].y_2],e[i].val);
		ans+=trl[1]*(e[i+1].x-e[i].x);
	}
	cout<<ans<<endl;
	return 0;
}
2024/12/21 18:41
加载中...