Submission #1296727

#TimeUsernameProblemLanguageResultExecution timeMemory
1296727rxlfd314Tower (JOI24_tower)C++20
25 / 100
190 ms16244 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  int N, Q, A, B; ll D;
  cin >> N >> Q >> D >> A >> B;
  vt<arl2> ranges, temp;
  ll pr = -1;
  FOR(i, 0, N - 1) {
    ll l, r;
    cin >> l >> r;
    if (pr + 1 < l)
      temp.push_back({pr + 1, l - 1});
    pr = r;
  }
  if (pr < 1e12)
    temp.push_back({pr + 1, (ll)1e12});
  
  vt<arl2> dp;
  vt<ll> dp2;
  const auto cost = [&](const ll x) -> arl2 {
    const int i = lower_bound(all(ranges), arl2{x + 1, 0}) - ranges.begin() - 1;
    if (x > ranges[i][1] || x < ranges[i][0])
      return {-1, -1};
    return {(ranges[i][0] + dp[i][1] <= x) * ((x - ranges[i][0] - dp[i][1]) / D + 1) + dp[i][0], dp2[i]};
  };
  
  ranges.push_back(temp[0]);
  dp.push_back({0, min(D, temp[0][1] - temp[0][0] + 1)});
  dp2.push_back(0);
  FOR(i, 1, size(temp) - 1) {
    int L = size(ranges), R = -1;
    ll lo = 0, hi = size(ranges);
    while (lo < hi) {
      const int mid = lo + hi >> 1;
      if (ranges[mid][1] + D >= temp[i][0])
        L = hi = mid;
      else
        lo = mid + 1;
    }
    lo = -1, hi = size(ranges) - 1;
    while (lo < hi) {
      const int mid = lo + hi + 1 >> 1;
      if (ranges[mid][0] + D <= temp[i][1])
        R = lo = mid;
      else
        hi = mid - 1;
    }
    if (L > R)
      continue;
    temp[i][0] = max(temp[i][0], ranges[L][0] + D);
    const auto [vv, vv2] = cost(temp[i][0] - D);
    dp2.push_back(vv2 + 1);
    
    lo = 0, hi = size(ranges);
    while (lo < hi) {
      const int mid = lo + hi >> 1;
      if (cost(ranges[mid][1])[0] > vv + 1)
        hi = mid;
      else
        lo = mid + 1;
    }
    if (lo == size(ranges)) {
      dp.push_back({vv + 1, min(D, temp[i][1] - temp[i][0] + 1)});
    } else {
      hi = ranges[lo][1], lo = ranges[lo][0];
      while (lo < hi) {
        const ll mid = lo + hi >> 1;
        if (cost(mid)[0] > vv + 1)
          hi = mid;
        else
          lo = mid + 1;
      }
      dp.push_back({vv + 1, min(D, lo + D - temp[i][0])});
    }
    ranges.push_back(temp[i]);
  }

  while (Q--) {
    ll x; cin >> x;
    const auto [a, b] = cost(x);
    cout << (a < 0 ? -1 : min((x - a * D) * A + a * B, (x - b * D) * A + b * B)) << '\n';
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...