Advertisement
Malinovsky239

Untitled

Sep 29th, 2013
143
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.40 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <cstdlib>
  5. #include <cstring>
  6. #include <string>
  7. #include <vector>
  8. #include <map>
  9. #include <set>
  10. #include <cmath>
  11. #include <ctime>
  12. #include <cassert>
  13.  
  14. using namespace std;
  15.  
  16. #define pb push_back
  17. #define mp make_pair
  18. #define sz(A) (int)(A).size()
  19.  
  20. typedef long long LL;
  21. typedef long double LD;
  22.  
  23. const int N = 1e5 + 10;
  24. const int SZ = 4 * N;
  25. const LL INF = (LL) 1e18;
  26.  
  27. int n, u, v, a[N];
  28. LL t[SZ], topush[SZ], delta[N];
  29.  
  30. void addVal (int v, int val)
  31. {
  32.     topush[v] += val;
  33.     t[v] += val;
  34. }
  35.  
  36. void push (int v)
  37. {
  38.     addVal(v * 2 + 1, topush[v]);
  39.     addVal(v * 2 + 2, topush[v]);
  40.  
  41.     topush[v] = 0;
  42. }
  43.  
  44. void build (int v, int l, int r)
  45. {
  46.     //cerr << v << ' ' << l << ' ' << r << endl;
  47.    
  48.     if (l + 1 == r) {
  49.         if (l == 0)
  50.             t[v] = delta[l];
  51.         else
  52.             t[v] = INF;
  53.    
  54.         return;
  55.     }
  56.  
  57.     int m = (l + r) / 2;
  58.    
  59.     build(v * 2 + 1, l, m);
  60.     build(v * 2 + 2, m, r);
  61.  
  62.     t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
  63. }
  64.  
  65. void add (int v, int l, int r, int L, int R, int val)
  66. {
  67.     if (L <= l && r <= R) {
  68.         addVal(v, val);
  69.         return;
  70.     }
  71.  
  72.     if (r <= L || R <= l)
  73.         return;
  74.  
  75.     push(v);
  76.     int m = (l + r) / 2;
  77.  
  78.     add(v * 2 + 1, l, m, L, R, val);
  79.     add(v * 2 + 2, m, r, L, R, val);
  80.  
  81.     t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
  82. }
  83.  
  84. LL get (int v, int l, int r, int L, int R)
  85. {
  86.     if (L <= l && r <= R)
  87.         return t[v];
  88.     if (r <= L || R <= l)
  89.         return INF;
  90.  
  91.     push(v);
  92.  
  93.     int m = (l + r) / 2;
  94.  
  95.     return min(get(v * 2 + 1, l, m, L, R), get(v * 2 + 2, m, r, L, R));
  96. }
  97.  
  98. void update (int v, int l, int r, int pos, LL val)
  99. {
  100.     if (l + 1 == r) {
  101.         t[v] = min(t[v], val);
  102.         return;
  103.     }
  104.  
  105.     push(v);
  106.     int m = (l + r) / 2;
  107.  
  108.     if (pos < m)
  109.         update(v * 2 + 1, l, m, pos, val);
  110.     else
  111.         update(v * 2 + 2, m, r, pos, val);
  112.  
  113.     t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
  114. }
  115.  
  116. int main()
  117. {
  118.     freopen("input.txt", "r", stdin);
  119.     freopen("output.txt", "w", stdout);
  120.    
  121.     scanf("%d%d%d", &n, &u, &v);
  122.  
  123.     for (int i = N - 3; i >= 0; i--) {
  124.         delta[i] = delta[i + 1] + v;
  125.     }
  126.  
  127.     for (int i = 0; i < n; i++) {
  128.         scanf("%d", a + i);
  129.     }
  130.  
  131.     build(0, 0, N);
  132.    
  133.     LL ans = n * u;
  134.     for (int i = 0; i < n; i++) {
  135.         LL cur_res = get(0, 0, N, 0, a[i]) - delta[a[i] - 1];
  136.         LL global = cur_res + u * (n - i - 1);
  137.  
  138.         ans = min(ans, global);
  139.    
  140.         add(0, 0, N, 0, N, u);
  141.         update(0, 0, N, a[i], cur_res + delta[a[i]]);
  142.     }
  143.  
  144.     cout << ans << endl;
  145.  
  146.    
  147.     return 0;
  148. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement