Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <vector>
- using namespace std;
- struct elem {
- long double l, r, total, sum;
- };
- const int oo = 3e5;
- vector <int> a(oo);
- vector <int> p(oo);
- vector <long double> mo(oo);
- vector <elem> b(oo * 2);
- elem q;
- elem sum(elem a, elem b){
- elem c;
- c.sum = a.sum + b.sum;
- c.l = max(a.l, a.sum + b.l);
- c.r = max(b.r, b.sum + a.r);
- c.total = max(max(a.total, b.total), a.r + b.l);
- return c;
- }
- elem gsum(int v, int ll, int rr, int l, int r){
- if (ll > r || l > rr)
- return q;
- if (l <= ll && rr <= r)
- return b[v];
- return sum(gsum(v * 2, ll, (ll + rr) / 2, l, r), gsum(v * 2 + 1, (ll + rr) / 2 + 1, rr, l, r));
- }
- int main(){
- int n, m, c, i, l, r, step;
- long double ans = 0, promres;
- q.total = q.l = q.r = q.sum = 0;
- cin >> n >> m >> c;
- for (i = 0; i < n; i++)
- cin >> a[i];
- for (i = 0; i < n - 1; i++)
- cin >> p[i];
- for (i = 0; i < n - 1; i++)
- mo[i] = (a[i + 1] - a[i]) / 2.0 - c * p[i] / 100.0;
- step = 1;
- while (step < n - 1)
- step *= 2;
- for (i = step; i < step + n - 1; i++){
- b[i].sum = mo[i - step];
- if (mo[i - step] > 0)
- b[i].l = b[i].r = b[i].total = mo[i - step];
- }
- for (i = step - 1; i > 0; i--){
- b[i] = sum(b[i * 2], b[i * 2 + 1]);
- }
- cout.precision(9);
- for (i = 0; i < m; i++){
- cin >> l >> r;
- promres = gsum(1, 1, step, l, r - 1).total;
- ans += promres;
- }
- cout << endl << fixed << ans;
- system("pause");
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement