CodeForces 151 E 스마트 치 터 (선분 수)
6504 단어 데이터 구조선분 수ACMcodeforces
E. Smart Cheater
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
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 [A, C] and [D, B], 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 n, m and c (2 ≤ n ≤ 1.5·105, 1 ≤ m ≤ 3·105, 1 ≤ c ≤ 104).
The next line contains n integers xi (0 ≤ xi ≤ 109, x1 = 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. The answer will be considered correct if its relative or absolute error does not exceed 10 - 6.
Sample test(s)
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
Note
A comment to the first sample:
The first and third passengers get tickets from stop 1 to stop 2. The second passenger doesn't get a ticket. There always is inspection on the segment 1-2 but both passengers have the ticket for it. There never is an inspection on the segment 2-3, that's why the second passenger gets away with the cheating. Our total profit is (0 + 90 / 2 + 90 / 2) = 90.
제목: 한 직선 에서 왼쪽 에서 오른쪽으로 N 개의 역 이 있 습 니 다. 각 점 의 좌표 X [i] 를 알 고 있 습 니 다. 자동 차 는 첫 번 째 역 에서 N 번 째 역 으로 갑 니 다. M 명의 승객 이 있 습 니 다. 모든 승객 은 ai 역 에서 bi 역 에서 내 렸 습 니 다. 표 값 은 X [bi] - X [ai] 입 니 다. 모든 승객 에 게 매표원 은 한 구간 [l, r] (선택 하지 않 아 도 됩 니 다) 을 선택 할 수 있 습 니 다.역 l 에서 역 r 구간 까지 의 표를 팔 지 않 고 나머지 전 매표원 과 승객 을 똑 같이 나눈다.
문제 풀이:
i 번 째 사람 에 게 매표원 이 그의 구간 [l, r] 표를 팔 지 않 으 면 그 가 돈 을 벌 기 를 바 라 는 것 은:
(X[r]-X[l])/2-(pl+......pr)*C/100
p 배열 의 접두사 와 배열 sump 를 처리 합 니 다.
다음 과 같이 쓸 수 있 습 니 다.
X[r]/2-sump[r]*c/100 - x[l]/2+sump[l-1]*C/100
다른 a [r] = X [r] / 2 - sump [r] * c / 100, b [l] = - x [l] / 2 + sump [l - 1] * C / 100
c [l, r] = a [r] + b [l] 및 l < r 우 리 는 선분 트 리 로 한 구간 에서 가장 큰 a, 가장 큰 b, 그리고 가장 큰 c 를 유지 한 다음 에 O (lgn) 로 조 회 를 완성 할 수 있 습 니 다.
코드 는 다음 과 같 습 니 다:
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
#include<string.h>
#include<string>
#include<stdlib.h>
typedef __int64 LL;
typedef unsigned __int64 LLU;
const int nn=310000;
const int inf=0x3fffffff;
const LL inf64=(LL)inf*inf;
const double eps=1e-8;
using namespace std;
LL n,m,c;
LL x[nn],p[nn];
LL mv1[nn*4],mv2[nn*4];
LL mans[nn*4];
LL sum[nn];
void update(int id)
{
mans[id]=mv1[2*id+1]+mv2[2*id];
mans[id]=max(mans[id],mans[2*id+1]);
mans[id]=max(mans[id],mans[2*id]);
mv1[id]=max(mv1[2*id],mv1[2*id+1]);
mv2[id]=max(mv2[2*id],mv2[2*id+1]);
}
void build(int id,int l,int r)
{
if(l==r)
{
mv1[id]=50*x[r]-c*sum[r-1];
mv2[id]=-50*x[l]+c*sum[l-1];
mans[id]=0;
return ;
}
int mid=(l+r)/2;
build(2*id,l,mid);
build(2*id+1,mid+1,r);
update(id);
}
vector<int>ve;
void solve(int id,int l,int r,int L,int R)
{
if(L<=l&&r<=R)
{
ve.push_back(id);
return ;
}
int mid=(l+r)/2;
if(L<=mid)
solve(2*id,l,mid,L,R);
if(R>mid)
solve(2*id+1,mid+1,r,L,R);
}
int main()
{
int i;
LL l,r;
while(scanf("%I64d%I64d%I64d",&n,&m,&c)!=EOF)
{
for(i=1;i<=n;i++)
{
scanf("%I64d",&x[i]);
}
sum[0]=0;
for(i=1;i<n;i++)
{
scanf("%I64d",&p[i]);
sum[i]=sum[i-1]+p[i];
}
build(1,1,n);
LL ans=0;
LL m1,m2,m3;
m1=m2=m3;
LL a1,a2,a3;
for(i=1;i<=m;i++)
{
scanf("%I64d%I64d",&l,&r);
ve.clear();
solve(1,1,n,l,r);
m1=mv1[ve[0]];
m2=mv2[ve[0]];
m3=mans[ve[0]];
for(int j=1;j<(int)ve.size();j++)
{
a3=max(m3,mans[ve[j]]);
a3=max(a3,mv1[ve[j]]+m2);
a1=max(m1,mv1[ve[j]]);
a2=max(m2,mv2[ve[j]]);
m1=a1,m2=a2,m3=a3;
}
ans+=m3;
}
printf("%lf
",ans/100.0);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.