P2065 - 「Poetize10」封印一擊
From lydliyudong Normal (OI)
總時限：10s 內存限制：128MB 代碼長度限制：64KB
背景 Background
“聖主applepi於公元2011年9月創造了Nescafe，它在散發了16次光輝之後與公元2011年11月12日被封印為一顆魂珠，貯藏於Nescafe神塔之中。公元2012年9月，聖主帶領四大護法重啟了Nescafe，如今已經是Nescafe之魂的第30次傳播了。不久，它就要被第二次封印，而變成一座神杯……”applepi思索著Nescafe的歷史，准備著第二次封印。 www.2cto.com
描述 Description
Nescafe由n種元素組成（編號為1~n），第i種元素有一個封印區間[ai,bi]。當封印力度E小於ai時，該元素將獲得ai的封印能量；當封印力度E在ai到bi之間時，該元素將獲得E的封印能量；而當封印力度E大於bi時，該元素將被破壞從而不能獲得任何封印能量。現在聖主applepi想選擇恰當的E，使得封印獲得的總能量盡可能高。為了封印的最後一擊盡量完美，就請你寫個程序幫他計算一下吧！
輸入格式 InputFormat
第一行一個整數N。
接下來N行每行兩個整數ai、bi，第i+1行表示第i種元素的封印區間。
輸出格式 OutputFormat
兩個用空格隔開的整數，第一個數是能夠獲得最多總能量的封印力度E，第二個數是獲得的總能量大小。當存在多個E能夠獲得最多總能量時，輸出最小的E。
樣例輸入 SampleInput [復制數據]
2
5 10
20 25
樣例輸出 SampleOutput [復制數據]
10 30
數據范圍和注釋 Hint
對於 50% 的數據，1<=N<=1000，1<=ai<=bi<=10000。
對於 100% 的數據，1<=N<=10^5，1<=ai<=bi<=10^9。
時間限制 TimeLimitation
各個測試點1s
區間選取
用Past和In_s維護經過的左右結點，
並由此算出
嵌套數（左-右）
左邊的區間數=右
右邊的區間數=總-（左-右）-右=總-左
PS:由於是閉區間，需要把-右的時間後延
[cpp]
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cctype>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (200000+10)
#define MAXAi (1000000000)
#define NDEBUG
struct segment_node
{
int l,type;
friend bool operator<(const segment_node a,const segment_node b){return (a.l!=b.l)?a.l<b.l:a.type<b.type; }
friend bool operator==(const segment_node a,const segment_node b){return (a.l==b.l&&a.type==b.type); }
friend bool operator!=(const segment_node a,const segment_node b){return (!(a==b)); }
}a[MAXN];
int n;
long long next[MAXN];
int main()
{
#ifndef NDEBUG
freopen("segmentbet.in","r",stdin);
#endif
memset(a,0,sizeof(a));
scanf("%d",&n);n<<=1;
for (int i=1;i<=n;i+=2)
{
scanf("%d%d",&a[i].l,&a[i+1].l);
a[i].type=-1;a[i+1].type=1;
}
sort(a+1,a+n+1);
int in_s=0,minE=0;
long long ans=0;
memset(next,0,sizeof(next));
for (int i=n-1;i>=1;i--)
{
next[i]=next[i+1];
if (a[i+1].type==-1)
next[i]+=a[i+1].l;
}
int j=1,past=0,pastE=0;
for (int i=1;i<=n;i++)
{
if (a[i]!=a[i+1])
{
int len=i-j+1;
j=i+1;
len*=-a[i].type;
if (pastE!=a[i].l) {in_s+=past;past=0;}
if (len>0) in_s+=len;
else past+=len;
long long cost=(long long)(long long)in_s*(long long)a[i].l+next[i];
if (ans<cost)
{
ans=cost;
minE=a[i].l;
}
}
}
cout<<minE<<' '<<ans<<endl;
return 0;
}
