• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

CodeForces-150C:SmartCheater(线段树,求最大连续区间)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

 

I guess there's not much point in reminding you that Nvodsk winters aren't exactly hot. That increased the popularity of the public transport dramatically. The route of bus 62 has exactly n stops (stop 1 goes first on its way and stop n goes last). The stops are positioned on a straight line and their coordinates are 0 = x1 < x2 < ... < xn.

Each day exactly m people use bus 62. For each person we know the number of the stop where he gets on the bus and the number of the stop where he gets off the bus. A ticket from stop a to stop b (a < b) costs xb - xa rubles. However, the conductor can choose no more than one segment NOT TO SELL a ticket for. We mean that conductor should choose C and D (С <= D) and sell a ticket for the segments [AC] and [DB], or not sell the ticket at all. The conductor and the passenger divide the saved money between themselves equally. The conductor's "untaxed income" is sometimes interrupted by inspections that take place as the bus drives on some segment of the route located between two consecutive stops. The inspector fines the conductor by c rubles for each passenger who doesn't have the ticket for this route's segment.

You know the coordinated of all stops xi; the numbers of stops where the i-th passenger gets on and off, ai and bi (ai < bi); the fine c; and also pi — the probability of inspection on segment between the i-th and the i + 1-th stop. The conductor asked you to help him make a plan of selling tickets that maximizes the mathematical expectation of his profit.

Input

The first line contains three integers nm and c (2 ≤ n ≤ 150 000, 1 ≤ m ≤ 300 000, 1 ≤ c ≤ 10 000).

The next line contains n integers xi (0 ≤ xi ≤ 109x1 = 0, xi < xi + 1) — the coordinates of the stops on the bus's route.

The third line contains n - 1 integer pi (0 ≤ pi ≤ 100) — the probability of inspection in percents on the segment between stop i and stop i + 1.

Then follow m lines that describe the bus's passengers. Each line contains exactly two integers ai and bi (1 ≤ ai < bi ≤ n) — the numbers of stops where the i-th passenger gets on and off.

Output

Print the single real number — the maximum expectation of the conductor's profit. 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 .

Examples

Input
3 3 10
0 10 100
100 0
1 2
2 3
1 3
Output
90.000000000
Input
10 8 187
0 10 30 70 150 310 630 1270 2550 51100
13 87 65 0 100 44 67 3 4
1 10
2 9
3 8
1 5
6 10
2 7
4 10
4 5
Output
76859.990000000

题意:有从左到右1到N个站,每一站到下一战的费用是两站间距离,即X[i+1]-X[i]。现在假设乘客从a站到b站,那么他可以和售票员密谋,不买其中连续一段的票,然后这些钱两人对半分。而每一站到下一站有被发现的几率为Pi,如果被发现就会罚款C元。有M个乘客,问售票员一共最多赚多少钱。

思路:乘客之间没有联系,单独考虑,我们保存每一站到下一站的收益,即X[i+1]-X[i]-Pi*C,那么现在问题转化为区间最大连续区间值。也就是裸的线段树题了。

手动打的丑代码:

#include<bits/stdc++.h>
#define piii pair<pair<double,double>,double>
#define F first
#define S second
using namespace std;
const int maxn=1000000;
double x[maxn],a[maxn];
double sum[maxn]; piii Mx[maxn];//0左,1右,2最大 
void build(int Now,int L,int R)
{
    if(L==R){
        sum[Now]=a[L]; Mx[Now].F.F=Mx[Now].F.S=a[L];
        Mx[Now].S=max(a[L],0.0);
        return ;
    }
    int Mid=(L+R)>>1;
    build(Now<<1,L,Mid); build(Now<<1|1,Mid+1,R);
    sum[Now]=sum[Now<<1]+sum[Now<<1|1];
    Mx[Now].F.F=max(Mx[Now<<1].F.F,sum[Now<<1]+Mx[Now<<1|1].F.F);
    Mx[Now].F.S=max(Mx[Now<<1|1].F.S,sum[Now<<1|1]+Mx[Now<<1].F.S);
    Mx[Now].S=max(max(Mx[Now<<1].S,Mx[Now<<1|1].S),Mx[Now<<1].F.S+Mx[Now<<1|1].F.F);
}
piii query(int Now,int L,int R,int l,int r)
{
    if(l<=L&&r>=R) return Mx[Now];
    int Mid=(L+R)/2;
    if(r<=Mid) return query(Now<<1,L,Mid,l,r);
    if(l>Mid) return query(Now<<1|1,Mid+1,R,l,r);
    else {
        piii res,tmp;
        res=query(Now<<1,L,Mid,l,r);
        tmp=query(Now<<1|1,Mid+1,R,l,r);
        res.S=max(max(res.S,tmp.S),res.F.S+tmp.F.F);
        res.F.F=max(res.F.F,sum[Now<<1]+tmp.F.F);
        res.F.S=max(tmp.F.S,sum[Now<<1|1]+res.F.S);
        return res;
    }
}
int main()
{
    int N,M,i; double C,P,ans=0;
    scanf("%d%d%lf",&N,&M,&C);
    for(i=1;i<=N;i++) scanf("%lf",&x[i]);
    for(i=1;i<N;i++){
        scanf("%lf",&P);
        a[i]=(x[i+1]-x[i])/2-C*P/100.0;
    }
    build(1,1,N-1);
    for(i=1;i<=M;i++){
        int L,R; scanf("%d%d",&L,&R); 
        ans+=query(1,1,N-1,L,R-1).S;
    }
    printf("%.8lf\n",ans);
    return 0;
}

以及别人的重载加法的令人赏心悦目的代码:

#include <stdio.h>
#define db double
const int N=150050;
const int M=2*N;
db max(db a, db b){ return a>b?a:b;}
struct Node
{
    db l,r,sum,best;
    Node(){}
    Node(db x){ l=r=best=max(x,0);sum=x;}
} node[M];
Node operator + (Node a, Node b)
{
    Node ans;
    ans.best=max(a.best,b.best);
    ans.best=max(ans.best,a.r+b.l);
    ans.sum=a.sum+b.sum;
    ans.l=max(a.l,a.sum+b.l);
    ans.r=max(b.r,b.sum+a.r);
    return ans;
}
db sub[N];
int ls[M],rs[M],tsz,root;
void Build(int &c, int ss, int se)
{
    c=++tsz;
    if(ss==se){ node[c]=Node(sub[ss]);return;}
    int mid=ss+se>>1;
    Build(ls[c],ss,mid);
    Build(rs[c],mid+1,se);
    node[c]=node[ls[c]]+node[rs[c]];
}
Node Get(int c, int ss, int se, int qs, int qe)
{
    if(qs<=ss && qe>=se) return node[c];
    int mid=ss+se>>1;
    if(qe<=mid) return Get(ls[c],ss,mid,qs,qe);
    if(qs>mid) return Get(rs[c],mid+1,se,qs,qe);
    return Get(ls[c],ss,mid,qs,qe)+Get(rs[c],mid+1,se,qs,qe);
}
int x[N],p[N];
int main()
{
    int n,m,c,i,l,r;
    scanf("%i %i %i",&n,&m,&c);
    for(i=1;i<=n;i++) scanf("%i",&x[i]);
    for(i=2;i<=n;i++) scanf("%i",&p[i]),sub[i]=(db)(x[i]-x[i-1])/2-(db)c*p[i]/100;
    Build(root,2,n);
    db sol=0;
    while(m--)
    {
        scanf("%i %i",&l,&r);
        sol+=Get(root,2,n,l+1,r).best;
        Node tmp=Get(root,2,n,l+1,r);
    }
    printf("%.12llf\n",sol);
    return 0;
}

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C#NotifyIcon托盘控件发布时间:2022-07-18
下一篇:
CodeforcesRound#270DCBA发布时间:2022-07-18
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap