제출 #1208127

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1208127		abczz	Tower (JOI24_tower)	C++20	0 / 100	2096 ms	2176 KiB

Main

#include <iostream>
#include <map>
#include <vector>
#include <array>
#define ll long long

using namespace std;

vector <array<ll, 2>> V, U;
vector <ll> T, W;
array<ll, 2> R[200000];
ll n, q, d, a, b, x, y, suff[200005], diff[200005], X[200005], Z[200005];

void fit(ll ql, ll qr) {
  ll l = 0, r = V.size()-1, mid;
  while (l < r) {
    mid = (l+r+1)/2;
    if (V[mid][0] <= ql) l = mid;
    else r = mid - 1;
  }
  if (V[l][0] <= ql) {
    if (V[l][1] >= ql) suff[l] = min(suff[l], ql);
    ql = l + 1;
  }
  else ql = l;
  l = 0, r = V.size()-1;
  while (l < r) {
    mid = (l+r+1)/2;
    if (V[mid][0] <= qr) l = mid;
    else r = mid - 1;
  }
  if (V[l][0] <= qr) {
    qr = l;
    if (ql <= qr) ++diff[ql], --diff[qr+1];
  }
}
ll reach(ll u) {
  ll l = 0, r = V.size()-1, mid;
  while (l < r) {
    mid = (l+r+1)/2;
    if (V[mid][0] <= u) l = mid;
    else r = mid - 1;
  }
  return l;
}
int main() {
  cin >> n >> q >> d >> a >> b;
  for (int i=0; i<n; ++i) {
    X[i] = Z[i] = -1;
    suff[i] = (ll)1e18;
    cin >> R[i][0] >> R[i][1];
  }
  for (int i=0; i+1<n; ++i) {
    V.push_back({R[i][1]+1, R[i+1][0]-1});
  }
  V.push_back({R[n-1][1]+1, (ll)1e18});
  fit(max(0LL, R[0][0]-d)+d, R[0][0]-1+d);
  ll s = 0;
  for (int i=0; i<V.size(); ++i) {
    s += diff[i];
    if (s || suff[i] == V[i][0]) {
      if (i != V.size()-1) fit(max(V[i][0], V[i][1]-d+1)+d, V[i][1]+d);
      U.push_back({V[i][0], V[i][1]});
    }
    else if (suff[i] != (ll)1e18) {
      if (i != V.size()-1) fit(max(suff[i], V[i][1]-d+1)+d, V[i][1]+d);
      U.push_back({suff[i], V[i][1]});
    }
  }
  swap(U, V);
  if (V.empty()) {
    while (q--) {
      cin >> x;
      cout << "-1\n";
    }
    return 0;
  }
  if (a*d <= b) {
    ll xl = max(0LL, R[0][0]-d), xr = R[0][0]-1;
    int i = 0;
    ll w = 0;
    while (i != (ll)V.size()-1) {
      ++w;
      xl += d, xr += d;
      while (V[i][1] < xl) ++i;
      xl = max(xl, V[i][0]);
      xr = V[reach(xr)][1];
      xl = max(xl, xr-d+1);
      X[i] = w;
    }
    for (int i=1; i<V.size(); ++i) {
      if (X[i] == -1) X[i] = X[i-1];
    }
    while (q--) {
      cin >> x;
      if (x < R[0][0]) cout << x * a << '\n';
      else {
        ll u = reach(x);
        if (x >= V[0][0] && x <= V[u][1]) cout << X[u] * b + (x - X[u] * d) * a << '\n';
        else cout << "-1\n";
      }
    }
  }
  else {
    T.push_back(0);
    ll cur = (ll)((R[0][0]-1)/d) * d;
    for (int i=0; i<V.size(); ++i) {
      if (cur + d >= V[i][0] && cur + d <= V[i][1]) {
        cur += (ll)((V[i][1]-cur) / d) * d;
      }
      else if (cur + d >= V[i][0]) continue;
      else {
        T.push_back(cur);
        if (V[reach(cur)][1]+d >= V[i][0]) {
          T.push_back(V[i][0]);
          cur = V[i][0] + (ll)((V[i][1]-V[i][0])/d) * d;
          continue;
        }
        for (int j=reach(cur)+1; j<V.size(); ++j) {
          x = reach(V[j][0]+d);
          y = reach(V[j][1]+d);
          if (V[j][0]+d <= V[x][1]) {
            T.push_back(V[j][0]+d);
            cur = V[j][0] + d + (ll)((V[x][1] - (V[j][0] + d))/d) * d;
            break;
          }
          else if (x != y) {
            T.push_back(V[x+1][0]);
            cur = V[x+1][0] + (ll)((V[x+1][1]-V[x+1][0])/d) * d;
            break;
          }
        }
      }
    }
    for (int i=0; i+1<T.size(); ++i) {
      if (!(i&1)) W.push_back((T[i+1]-T[i])/d);
      else W.push_back(1);
      if (W.size() > 1) W[(ll)W.size()-1] += W[(ll)W.size()-2];
    }
    while (q--) {
      cin >> x;
      if (x < R[0][0]) {
        cout << (ll)(x/d) * b + (x % d) * a << '\n';
        continue;
      }
      ll u = reach(x);
      if (x >= V[0][0] && x <= V[u][1]) {
        ll l = 0, r = T.size()-1, mid;
        while (l < r) {
          mid = (l+r+1)/2;
          if (x >= T[mid]) l = mid;
          else r = mid-1;
        }
        ll f = (l ? W[l-1] : 0);
        f += (x-T[l])/d;
        cout << f * b + (x - f * d) * a << '\n';
      }
      else cout << "-1\n";
    }
  }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 38
• Subtask 3: 0 / 25
• Subtask 4: 0 / 32