peltorator

!ДО из CHT

Jan 16th, 2018
156
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <math.h>
  5. #include <cmath>
  6. #include <cstdio>
  7. #include <string>
  8. #include <cstring>
  9. #include <queue>
  10.  
  11. using namespace std;
  12.  
  13. typedef long long ll;
  14. typedef long double ld;
  15.  
  16. const int MAXN = 1000000;
  17.  
  18. ll kk[MAXN], bb[MAXN];
  19.  
  20. vector<ll> k[MAXN], b[MAXN];
  21.  
  22. ld f(ld k1, ld b1, ld k2, ld b2)
  23. {
  24.     return (b1 - b2) / (k2 - k1);
  25. }
  26.  
  27. void addLine(int v, ll k1, ll b1)
  28. {
  29.     while (k[v].size() > 1)
  30.     {
  31.         ld cur = f(k1, b1, k[v].back(), b[v].back());
  32.         ld was = f(k[v].back(), b[v].back(), k[v][k[v].size() - 2], b[v][b[v].size() - 2]);
  33.         if (k1 == k[v].back() || cur < was)
  34.         {
  35.             k[v].pop_back();
  36.             b[v].pop_back();
  37.         }
  38.         else
  39.             break;
  40.     }
  41.     if (k[v].size() && k[v].back() == k1)
  42.     {
  43.         k[v].pop_back();
  44.         b[v].pop_back();
  45.     }
  46.     k[v].push_back(k1);
  47.     b[v].push_back(b1);
  48. }
  49.  
  50. void merge(int v)
  51. {
  52.     int i = 0, j = 0;
  53.     while (i < k[2 * v].size() || j < k[2 * v + 1].size())
  54.     {
  55.         if (i >= k[2 * v].size() || (j < k[2 * v + 1].size() &&
  56.                     (k[2 * v + 1][j] > k[2 * v][i] || (k[2 * v + 1][j] == k[2 * v][i] && b[2 * v + 1][j] > b[2 * v][i]))))
  57.         {
  58.             addLine(v, k[2 * v + 1][j], b[2 * v + 1][j]);
  59.             j++;
  60.         }
  61.         else
  62.         {
  63.             addLine(v, k[2 * v][i], b[2 * v][i]);
  64.             i++;
  65.         }
  66.     }
  67. }
  68.  
  69. void buildtree(int v, int l, int r)
  70. {
  71.     if (r < l)
  72.         return;
  73.     k[v].clear();
  74.     b[v].clear();
  75.     if (l == r)
  76.     {
  77.         k[v].push_back(kk[l]);
  78.         b[v].push_back(bb[l]);
  79.         return;
  80.     }
  81.     int mid = (r + l) / 2;
  82.     buildtree(2 * v, l, mid);
  83.     buildtree(2 * v + 1, mid + 1, r);
  84.     merge(v);
  85. }
  86.  
  87. ll tf(int v, int l, int r, int ql, int qr, ll x)
  88. {
  89.     if (r < l || ql > r || l > qr)
  90.         return 1e18;
  91.     if (ql <= l && r <= qr)
  92.     {
  93.       //  cout << "...." << l << " " << r << "...\n";
  94.        // for (int i = 0; i < k[v].size(); i++)
  95.          //   cout << k[v][i] << " " << b[v][i] << endl;
  96.         int left = 0, right = k[v].size();
  97.         while (right - left > 1)
  98.         {
  99.             int mid = (right + left) / 2;
  100.             if (f(k[v][mid - 1], b[v][mid - 1], k[v][mid], b[v][mid]) > (ld)x)
  101.                 right = mid;
  102.             else
  103.                 left = mid;
  104.         }
  105.         return k[v][left] * x + b[v][left];
  106.     }
  107.     int mid = (r + l) / 2;
  108.     return min(tf(2 * v, l, mid, ql, qr, x), tf(2 * v + 1, mid + 1, r, ql, qr, x));
  109. }
  110.  
  111. int main()
  112. {
  113.   //  freopen("in.txt", "r", stdin);
  114.     int n;
  115.     cin >> n;
  116.     vector<ll> a(n + 1, 0), sum(n + 1, 0);
  117.     for (int i = 1; i <= n; i++)
  118.     {
  119.         cin >> a[i];
  120.         sum[i] = sum[i - 1] + a[i];
  121.         kk[i] = a[i];
  122.         bb[i] = i * a[i] - sum[i];
  123.     }
  124.    //return 0;
  125.     buildtree(1, 1, n);
  126.    // return 0;
  127.     int m;
  128.     cin >> m;
  129. //    return 0;
  130.     vector<ll> ans(m);
  131.     for (int k = 0; k < m; k++)
  132.     {
  133.         int i, j;
  134.         cin >> i >> j;
  135.        // return 0;
  136.         ans[k] = sum[j] + tf(1, 1, n, max(1, j - i), j, i - j);
  137.         //cout << "-----------\n";
  138.       //return 0;
  139.     }
  140.  //   return 0;
  141.     for (int i = 0; i < m; i++)
  142.         cout << ans[i] << "\n";
  143.     return 0;
  144. }
RAW Paste Data