D. Babaei and Birthday Cake

题目连接：

http://www.codeforces.com/contest/629/problem/D

Description

As you know, every birthday party has a cake! This time, Babaei is going to prepare the very special birthday party's cake.

Simple cake is a cylinder of some radius and height. The volume of the simple cake is equal to the volume of corresponding cylinder. Babaei has n simple cakes and he is going to make a special cake placing some cylinders on each other.

However, there are some additional culinary restrictions. The cakes are numbered in such a way that the cake number i can be placed only on the table or on some cake number j where j < i. Moreover, in order to impress friends Babaei will put the cake i on top of the cake j only if the volume of the cake i is strictly greater than the volume of the cake j.

Babaei wants to prepare a birthday cake that has a maximum possible total volume. Help him find this value.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of simple cakes Babaei has.

Each of the following n lines contains two integers ri and hi (1 ≤ ri, hi ≤ 10 000), giving the radius and height of the i-th cake.

Output

Print the maximum volume of the cake that Babaei can make. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if .

Sample Input

2

100 30

40 10

Sample Output

942477.796077000

Hint

题意

有n个蛋糕，然后第i个蛋糕只能放在地上或者放在体积和编号都比他小的上面

然后问你体积最多能堆多大？

题解：

用线段树维护DP

显然这个东西和lis（最长上升子序列）有一点像

我们首先把每个东西的体积都离散化一下，然后我们选取比他小的最大值，然后进行更新就好了

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5+6;

typedef double SgTreeDataType;

struct treenode

{

  int L , R  ;

  double sum;

  int num;

  void updata(SgTreeDataType v)

  {

    sum += v;

  }

};

treenode tree[500000];

inline void push_down(int o)

{

}

inline void push_up(int o)

{

    tree[o].sum = max(tree[2*o].sum , tree[2*o+1].sum);

	if(tree[2*o].sum>tree[2*o+1].sum)

        tree[o].num=tree[2*o].num;

    else

        tree[o].num=tree[2*o+1].num;

}

inline void build_tree(int L , int R , int o)

{

	tree[o].L = L , tree[o].R = R,tree[o].sum = 0;

	tree[o].num = L;

	if (R > L)

	{

		int mid = (L+R) >> 1;

		build_tree(L,mid,o*2);

		build_tree(mid+1,R,o*2+1);

	}

}

inline void updata2(int QL,int QR,SgTreeDataType v,int o)

{

	int L = tree[o].L , R = tree[o].R;

	if (QL <= L && R <= QR)

    {

        tree[o].sum=max(tree[o].sum,v);

    }

	else

	{

		push_down(o);

		int mid = (L+R)>>1;

		if (QL <= mid) updata2(QL,QR,v,o*2);

		if (QR >  mid) updata2(QL,QR,v,o*2+1);

		push_up(o);

	}

}

inline SgTreeDataType query(int QL,int QR,int o)

{

    if(QR<QL)return 0;

	int L = tree[o].L , R = tree[o].R;

	if (QL <= L && R <= QR) return tree[o].sum;

	else

	{

		push_down(o);

		int mid = (L+R)>>1;

		SgTreeDataType res = 0;

		if (QL <= mid) res = max(query(QL,QR,2*o),res);

		if (QR > mid) res = max(query(QL,QR,2*o+1),res);

		push_up(o);

		return res;

	}

}

double h[maxn],r[maxn],v[maxn];

const double pi = acos(-1.0);

vector<double>V;

map<double,int> H;

int main()

{

    int n;

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

    {

        scanf("%lf%lf",&r[i],&h[i]),v[i]=pi*r[i]*r[i]*h[i];

        V.push_back(v[i]);

    }

    sort(V.begin(),V.end());

    V.erase(unique(V.begin(),V.end()),V.end());

    for(int i=0;i<V.size();i++)

        H[V[i]]=i+1;

    build_tree(1,n,1);

    for(int i=1;i<=n;i++)

    {

        double p = v[i]+query(1,H[v[i]]-1,1);

        updata2(H[v[i]],H[v[i]],p,1);

    }

    printf("%.12f\n",tree[1].sum);

    return 0;

}