Advertisement
Guest User

Untitled

a guest
Apr 1st, 2024
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.05 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <numeric>
  4. #include <cassert>
  5. #include <vector>
  6. #include <map>
  7. #include <set>
  8.  
  9. typedef long long llong;
  10. const int MAXN = 200000 + 10;
  11. const llong INF = 1e18;
  12.  
  13. int n, q;
  14. int a, b;
  15. llong d;
  16. llong minJumps[MAXN];
  17.  
  18. std::vector <std::pair <llong,llong>> inp;
  19. std::vector <std::pair <llong,llong>> v;
  20.  
  21. bool inInterval(llong x)
  22. {
  23.     int l = -1, r = v.size(), mid;
  24.     while (l < r - 1)
  25.     {
  26.         mid = (l + r) / 2;
  27.         if (v[mid].second < x) l = mid;
  28.         else r = mid;
  29.     }
  30.  
  31.     return r != v.size() && v[r].first <= x;
  32. }
  33.  
  34. int getInterval(llong x)
  35. {
  36.     int l = -1, r = v.size(), mid;
  37.     while (l < r - 1)
  38.     {
  39.         mid = (l + r) / 2;
  40.         if (v[mid].second < x) l = mid;
  41.         else r = mid;
  42.     }
  43.  
  44.     return r;
  45. }
  46.  
  47. std::map <llong, llong> dp;
  48. llong findClosest(llong x)
  49. {
  50.     int l = -1, r = v.size(), mid;
  51.     while (l < r - 1)
  52.     {
  53.         mid = (l + r) / 2;
  54.         if (v[mid].second <= x) l = mid;
  55.         else r = mid;
  56.     }
  57.  
  58.     assert(l != -1);
  59.     return v[l].second;
  60. }
  61.  
  62. llong calcMAX(llong x)
  63. {
  64.     if (dp.count(x))
  65.     {
  66.         return dp[x];
  67.     }
  68.  
  69.     assert(inInterval(x));
  70.     if (x < d)
  71.     {
  72.         return x * a;
  73.     }
  74.  
  75.     int idx = getInterval(x);
  76.     if (x - v[idx].first >= d)
  77.     {
  78.         llong times = (x - v[idx].first) / d;
  79.         return dp[x] = calcMAX(x - times * d) + times * b;
  80.     }
  81.  
  82.     if (inInterval(x - d))
  83.     {
  84.         dp[x] = calcMAX(x - d) + b;
  85.     } else
  86.     {  
  87.         llong closest = findClosest(x - d);
  88.         dp[x] = calcMAX(closest) + b + (x - closest - d) * a;
  89.     }
  90.  
  91.     return dp[x];
  92. }
  93.  
  94. void solve()
  95. {
  96.     v.push_back(inp[0]);
  97.     inp.erase(inp.begin());
  98.     for (const auto &[l, r] : inp)
  99.     {
  100.         int ll = -1, rr = v.size(), mid;
  101.         while (ll < rr - 1)
  102.         {
  103.             mid = (ll + rr) / 2;
  104.             if (v[mid].second + d < l) ll = mid;
  105.             else rr = mid;
  106.         }
  107.  
  108.         if (rr != v.size() && std::max(v[rr].first + d, l) <= r)
  109.         {
  110.             minJumps[v.size()] = minJumps[rr] + 1;
  111.             v.push_back({std::max(v[rr].first + d, l), r});
  112.         }
  113.     }
  114.  
  115.     for (int i = 1 ; i <= q ; ++i)
  116.     {
  117.         llong x;
  118.         std::cin >> x;
  119.         if (inInterval(x))
  120.         {
  121.             int r = getInterval(x);
  122.             std::cout << std::min(calcMAX(x), a * (x - minJumps[r] * d) + b * minJumps[r]) << '\n';
  123.         } else
  124.         {
  125.             std::cout << -1 << '\n';
  126.         }
  127.     }
  128. }
  129.  
  130. void input()
  131. {
  132.     std::cin >> n >> q;
  133.     std::cin >> d >> a >> b;
  134.  
  135.     llong last = -1;
  136.     for (int i = 1 ; i <= n ; ++i)
  137.     {
  138.         llong l, r;
  139.         std::cin >> l >> r;
  140.         if (last + 1 < l) inp.push_back({last + 1, l - 1});
  141.         last = r;
  142.     }
  143.  
  144.     if (last < INF) inp.push_back({last + 1, INF});
  145. }
  146.  
  147. void fastIOI()
  148. {
  149.     std::ios_base :: sync_with_stdio(0);
  150.     std::cout.tie(nullptr);
  151.     std::cin.tie(nullptr);
  152. }
  153.  
  154. int main()
  155. {
  156.     fastIOI();
  157.     input();
  158.     solve();
  159.  
  160.     return 0;
  161. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement