Symmetrical Painting

The first line of input contains a single integer N (1 <= N <= 300000), denoting the number of rectangles.

The next N lines of input contain two space-separated integers each, denoting L_i, R_i (1 <= L_i < R_i <= 10⁹).

C++14(g++5.4) 解法, 执行用时: 181ms, 内存消耗: 7656K, 提交时间: 2019-08-19 11:05:19

#include<bits/stdc++.h>
using namespace std;
const int N=300010;
typedef long long LL;
LL a[N*3],n,curans,ans,lst,num;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(LL l,r,i=0;i<n;i++){
		cin>>l>>r;
		a[i*3]=l<<2;
		a[i*3+1]=r<<2;
		a[i*3+2]=(l+r)*2+1;
	}
	sort(a,a+3*n);
	for(int i=0;i<n*3;i++){
		curans+=(a[i]/2-lst)*num;
		ans=max(ans,curans);
		lst=a[i]/2;
		if(a[i]&1)num-=2;
		else num++;
	}cout<<ans<<endl;
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 176ms, 内存消耗: 7528K, 提交时间: 2019-08-15 13:43:16

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll b[900005],l,r,n,ma,xl,nu,la;
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>l>>r;
		b[i*3]=l*4;
		b[i*3+1]=r*4;
		b[i*3+2]=(l+r)*2+1;
	}
	sort(b,b+n*3);
	ma=0;xl=0;nu=0;la=0;
	for(int i=0;i<n*3;i++){
		nu+=((b[i]/2)-la)*xl;
		ma=max(ma,nu);
		la=b[i]/2;
		if(b[i]&1){
			xl-=2;
		}else{
			xl++;
		}
	}
	cout<<ma;
	
}

详情