fork download 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <iostream>
  5. #include <iomanip>
  6. #include <sstream>
  7. #include <string>
  8. #include <vector>
  9. #include <algorithm>
  10. #include <queue>
  11. #include <stack>
  12. #include <set>
  13.  
  14. using namespace std;
  15.  
  16. double F[150000],P[150000];
  17. double Fmn[150000],Fmx[150000],Fans[150000];
  18. int p[150000];
  19.  
  20. int main(){
  21.     int n,m,C;
  22.  
  23.     scanf("%d %d %d",&n,&m,&C);
  24.  
  25.     int x[n];
  26.  
  27.     for(int i = 0;i < n;++i) scanf("%d",&x[i]);
  28.     for(int i = 1;i < n;++i) scanf("%d",&p[i]);
  29.  
  30.     P[0] = 0;
  31.     for(int i = 1;i < n;++i)
  32.         P[i] = P[i - 1] + p[i] / 100.0;
  33.  
  34.     for(int i = 0;i < n;++i)
  35.         F[i] = x[i] / 2.0 - C * P[i];
  36.  
  37.     int sz = (int)floor(sqrt(n));
  38.  
  39.     for(int i = 0;sz*i < n;i++){
  40.         Fmn[i] = F[sz*i];
  41.         Fmx[i] = F[sz*i];
  42.         Fans[i] = 0;
  43.         double mn = F[sz*i];
  44.  
  45.         for(int j = 0;j < sz && sz*i + j  < n;++j){
  46.             Fmn[i] = min(Fmn[i],F[sz*i + j]);
  47.             Fmx[i] = max(Fmx[i],F[sz*i + j]);
  48.  
  49.             mn = min(mn,F[sz*i + j]);
  50.             Fans[i] = max(Fans[i],F[sz*i + j] - mn);
  51.         }
  52.     }
  53.  
  54.     double ans = 0;
  55.  
  56.     for(int i = 0,xa,xb;i < m;++i){
  57.         scanf("%d %d",&xa,&xb);
  58.         --xa; --xb;
  59.  
  60.         double aux = 0;
  61.         int l = (xa + sz - 1) / sz,r = xb / sz;
  62.  
  63.         for(int j = l;j < r;++j)
  64.             aux = max(aux,Fans[j]);
  65.  
  66.         int x1 = sz * l;
  67.         double mn = F[xa];
  68.  
  69.         for(int j = xa;j < x1;++j){
  70.             mn = min(mn,F[j]);
  71.             aux = max(aux,F[j] - mn);
  72.         }
  73.  
  74.         for(int j = l;j < r;++j){
  75.             aux = max(aux,Fmx[j] - mn);
  76.             mn = min(mn,Fmn[j]);
  77.         }
  78.  
  79.         int x2 = sz * r;
  80.  
  81.         for(int j = x2;j <= xb;++j){
  82.             mn = min(mn,F[j]);
  83.             aux = max(aux,F[j] - mn);
  84.         }
  85.  
  86.         ans += aux;
  87.     }
  88.  
  89.     printf("%.8f\n",ans);
  90.  
  91.     return 0;
  92. }
  93.  
Runtime error #stdin #stdout 0.01s 9168KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/y2kEV
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!