Submission #978224

#	Time	Username	Problem	Language	Result	Execution time	Memory
978224		model_code	Tower (JOI24_tower)	C++17	100 / 100	1223 ms	116128 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
const long long INF = 3000000000000000000;
const int INF2 = 1000000;
struct lazy_segment_tree{
  int N;
  std::vector<int> ST;
  std::vector<int> lazy;
  lazy_segment_tree(int N2){
    N = 1;
    while (N < N2){
      N *= 2;
    }
    ST = std::vector<int>(N * 2 - 1, INF2);
    lazy = std::vector<int>(N * 2 - 1, -1);
  }
  void push(int i, int l, int r){
    if (lazy[i] != -1){
      if (i < N - 1){
        lazy[i * 2 + 1] = lazy[i];
        lazy[i * 2 + 2] = lazy[i];
      }
      if (lazy[i] == 0){
        ST[i] = INF2;
      }
      if (lazy[i] == 1){
        ST[i] = l;
      }
      lazy[i] = -1;
    }
  }
  void range_update(int L, int R, int x, int i, int l, int r){
    push(i, l, r);
    if (r <= L || R <= l){
      return;
    } else if (L <= l && r <= R){
      lazy[i] = x;
      push(i, l, r);
    } else {
      int m = (l + r) / 2;
      range_update(L, R, x, i * 2 + 1, l, m);
      range_update(L, R, x, i * 2 + 2, m, r);
      ST[i] = std::min(ST[i * 2 + 1], ST[i * 2 + 2]);
    }
  }
  void range_update(int L, int R, int x){
    range_update(L, R, x, 0, 0, N);
  }
  int query(int L, int R, int i, int l, int r){
    push(i, l, r);
    if (r <= L || R <= l){
      return INF2;
    } else if (L <= l && r <= R){
      return ST[i];      
    } else {
      int m = (l + r) / 2;
      return std::min(query(L, R, i * 2 + 1, l, m), query(L, R, i * 2 + 2, m, r));
    }
  }
  int query(int L, int R){
    return query(L, R, 0, 0, N);
  }
  bool operator [](int k){
    return query(k, k + 1) != INF2;
  }
};
int main(){
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int N, Q;
  std::cin >> N >> Q;
  long long D, A, B;
  std::cin >> D >> A >> B;
  B -= A * D;
  std::vector<long long> L(N), R(N);
  for (int i = 0; i < N; i++){
    std::cin >> L[i] >> R[i];
    R[i]++;
  }
  std::vector<long long> X(Q);
  for (int i = 0; i < Q; i++){
    std::cin >> X[i];
  }
  std::vector<long long> x, y;
  x.push_back(0);
  y.push_back(0);
  for (int i = 0; i < N; i++){
    x.push_back(L[i] / D);
    x.push_back(L[i] / D + 1);
    x.push_back(R[i] / D);
    x.push_back(R[i] / D + 1);
    x.push_back(R[i] / D + 2);
    y.push_back(L[i] % D);
    y.push_back(R[i] % D);
  }
  for (int i = 0; i < Q; i++){
    x.push_back(X[i] / D);
    y.push_back(X[i] % D);
  }
  std::sort(x.begin(), x.end());
  x.erase(std::unique(x.begin(), x.end()), x.end());
  std::sort(y.begin(), y.end());
  y.erase(std::unique(y.begin(), y.end()), y.end());
  int H = x.size();
  int W = y.size();
  std::vector<int> lx(N), ly(N), rx(N), ry(N);
  for (int i = 0; i < N; i++){
    lx[i] = std::lower_bound(x.begin(), x.end(), L[i] / D) - x.begin();
    ly[i] = std::lower_bound(y.begin(), y.end(), L[i] % D) - y.begin();
    rx[i] = std::lower_bound(x.begin(), x.end(), R[i] / D) - x.begin();
    ry[i] = std::lower_bound(y.begin(), y.end(), R[i] % D) - y.begin();
  }
  std::vector<long long> ans(Q, 0);
  std::vector<int> qx(Q), qy(Q);
  for (int i = 0; i < Q; i++){
    qx[i] = std::lower_bound(x.begin(), x.end(), X[i] / D) - x.begin();
    qy[i] = std::lower_bound(y.begin(), y.end(), X[i] % D) - y.begin();
    ans[i] = A * X[i] + std::min(B, (long long) 0) * (X[i] / D - qx[i]);
  }
  std::vector<std::vector<int>> ng(H);
  for (int i = 0; i < N; i++){
    ng[lx[i]].push_back(ly[i]);
    for (int j = lx[i]; j < rx[i]; j++){
      ng[j].push_back(W);
      ng[j + 1].push_back(0);
    }
    if (ry[i] == 0){
      ng[rx[i]].pop_back();
    } else {
      ng[rx[i]].push_back(ry[i]);
    }
  }
  std::vector<std::vector<int>> ok(H);
  for (int i = 0; i < H; i++){
    ok[i].push_back(0);
    for (int j : ng[i]){
      if (j == 0){
        ok[i].pop_back();
      } else {
        ok[i].push_back(j);        
      }
    }
    if (ok[i].back() == W){
      ok[i].pop_back();
    } else {
      ok[i].push_back(W);
    }
  }
  std::vector<std::vector<int>> query(H);
  for (int i = 0; i < Q; i++){
    query[qx[i]].push_back(i);
  }
  lazy_segment_tree dp(W);
  dp.range_update(0, 1, 1);
  int a = -1, b = 0;
  for (int i = 0; i < H; i++){
    if (i > 0){
      bool pr = dp[W - 1];
      int cnt_ng = ng[i].size();
      for (int j = 0; j < cnt_ng; j += 2){
        dp.range_update(ng[i][j], ng[i][j + 1], 0);
      }
      if (!ok[i].empty()){
        if (ok[i][0] == 0){
          if (pr){
            if (!dp[0] || B > 0){
              b = std::max(b, 1);
            }
            dp.range_update(0, 1, 1);
          }
        }
      }
    }
    int cnt_ok = ok[i].size();
    for (int j = 0; j < cnt_ok; j += 2){
      int idx = dp.query(ok[i][j], ok[i][j + 1]);
      if (idx != INF2){
        if (idx < b && b < ok[i][j + 1]){
          int next_b = ok[i][j + 1];
          if (B < 0){
            next_b = dp.query(b, ok[i][j + 1]);
            if (next_b == INF2){
              next_b = ok[i][j + 1];
            }
          }
          b = next_b;
        }
        dp.range_update(idx, ok[i][j + 1], 1);
      }
    }
    for (int j : query[i]){
      if (!dp[qy[j]]){
        ans[j] = -1;
      } else {
        ans[j] += (qy[j] < b ? B * a : B * (a + 1)) + B * i;
      }
    }
    if (b == W){
      b = 0;
      a--;
    }
  }
  for (int i = 0; i < Q; i++){
    std::cout << ans[i] << '\n';
  }
}

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