//上图绿色扫描线右侧少画了一条扫描线。
很多区间把数轴分成了很多段,看哪个点的(区间覆盖数*该点权值)最大。
显然在某个区间的右端点的答案是最优的。
排序后 用扫描线从左到右扫描,维护每个点的覆盖数,就是遇到左端点时cnt++,右端点时更新ans、cnt--。
若某个点既有左端点,又有右端点,就把左端点放在前面。
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
#define N 100001
ll ans;
int t1,t2,m,cnt,n;
struct Node{int v;bool dir;Node(const int &a,const bool &b){v=a;dir=b;}Node(){}}a[N<<];
bool operator < (const Node &a,const Node &b){return a.v!=b.v?a.v<b.v:a.dir<b.dir;}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d",&t1,&t2);
a[++m]=Node(t1,); a[++m]=Node(t2,);
}
sort(a+,a+m+);
for(int i=;i<=m;i++)
{
if(!a[i].dir) cnt++;
else
{
ans=max(ans,(ll)cnt*(ll)a[i].v);
cnt--;
}
}
cout<<ans<<endl;
return ;
}