Advertisement
noler89

Untitled

Dec 5th, 2015
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.44 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <vector>
  5. using namespace std;
  6. struct elem {
  7. long double l, r, total, sum;
  8. };
  9.  
  10. const int oo = 3e5;
  11. vector <int> a(oo);
  12. vector <int> p(oo);
  13. vector <long double> mo(oo);
  14. vector <elem> b(oo * 2);
  15. elem q;
  16.  
  17.  
  18. elem sum(elem a, elem b){
  19. elem c;
  20. c.sum = a.sum + b.sum;
  21. c.l = max(a.l, a.sum + b.l);
  22. c.r = max(b.r, b.sum + a.r);
  23. c.total = max(max(a.total, b.total), a.r + b.l);
  24. return c;
  25. }
  26.  
  27. elem gsum(int v, int ll, int rr, int l, int r){
  28. if (ll > r || l > rr)
  29. return q;
  30. if (l <= ll && rr <= r)
  31. return b[v];
  32. return sum(gsum(v * 2, ll, (ll + rr) / 2, l, r), gsum(v * 2 + 1, (ll + rr) / 2 + 1, rr, l, r));
  33. }
  34.  
  35.  
  36. int main(){
  37. int n, m, c, i, l, r, step;
  38. long double ans = 0, promres;
  39. q.total = q.l = q.r = q.sum = 0;
  40. cin >> n >> m >> c;
  41. for (i = 0; i < n; i++)
  42. cin >> a[i];
  43. for (i = 0; i < n - 1; i++)
  44. cin >> p[i];
  45. for (i = 0; i < n - 1; i++)
  46. mo[i] = (a[i + 1] - a[i]) / 2.0 - c * p[i] / 100.0;
  47. step = 1;
  48. while (step < n - 1)
  49. step *= 2;
  50. for (i = step; i < step + n - 1; i++){
  51. b[i].sum = mo[i - step];
  52. if (mo[i - step] > 0)
  53. b[i].l = b[i].r = b[i].total = mo[i - step];
  54. }
  55. for (i = step - 1; i > 0; i--){
  56. b[i] = sum(b[i * 2], b[i * 2 + 1]);
  57. }
  58. cout.precision(9);
  59. for (i = 0; i < m; i++){
  60. cin >> l >> r;
  61. promres = gsum(1, 1, step, l, r - 1).total;
  62. ans += promres;
  63. }
  64. cout << endl << fixed << ans;
  65. system("pause");
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement