제출 #282462

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
282462		rama_pang	Long Distance Coach (JOI17_coach)	C++14	100 / 100	488 ms	33528 KiB

coach

#include <bits/stdc++.h>
using namespace std;

using lint = __int128_t;
const lint INF = 8e18;
const int MAXN = 2e5 + 5;

template<typename A, typename B>
void chmin(A &a, const B &b) { a = min(a, b); }

template<typename A, typename B>
void chmax(A &a, const B &b) { a = max(a, b); }

__int128_t ReadInt() {
  long long x;
  cin >> x;
  return (__int128_t) x;
}

void Write(__int128_t x) {
  cout << (long long) x << "\n";
}

struct Line {
  lint a, b;
  Line() : a(0), b(INF) {}
  Line(lint a, lint b) : a(a), b(b) {}
  lint get(lint x) {
    return a * x + b;
  }
};

class LiChao {
 private:
  struct Node {
    Line line = Line();
    Node *lc = nullptr;
    Node *rc = nullptr;
  };

  lint sz;
  Node *root = nullptr;

  void InsertLineKnowingly(Node* &n, lint tl, lint tr, Line x) {
    if (n == nullptr) n = new Node();
    if (n->line.get(tl) > x.get(tl)) swap(n->line, x);
    if (n->line.get(tr) <= x.get(tr)) return;
    if (tl == tr) return;
    lint mid = (tl + tr) / 2;
    if (n->line.get(mid) < x.get(mid)) {
      InsertLineKnowingly(n->rc, mid + 1, tr, x);
    } else {
      swap(n->line, x);
      InsertLineKnowingly(n->lc, tl, mid, x);
    }
  }

  void InsertLine(Node* &n, lint tl, lint tr, lint l, lint r, Line x) {
    if (tr < l || r < tl || tl > tr || l > r) return;
    if (n == nullptr) n = new Node();
    if (l <= tl && tr <= r) return InsertLineKnowingly(n, tl, tr, x);
    lint mid = (tl + tr) / 2;
    InsertLine(n->lc, tl, mid, l, r, x);
    InsertLine(n->rc, mid + 1, tr, l, r, x);
  }

  lint Query(Node* &n, lint tl, lint tr, lint x) {
    if (n == nullptr) return INF;
    if (tl == tr) return n->line.get(x);
    lint res = n->line.get(x);
    lint mid = (tl + tr) / 2;
    if (x <= mid) {
      res = min(res, Query(n->lc, tl, mid, x));
    } else {
      res = min(res, Query(n->rc, mid + 1, tr, x));
    }
    return res;
  }

 public:
  LiChao() {}
  LiChao(lint sz) : sz(sz) {}

  void InsertLine(lint l, lint r, Line x) {
    return InsertLine(root, 0, sz - 1, l, r, x);
  }
  lint Query(lint x) {
    return min(INF, Query(root, 0, sz - 1, x));
  }
};

int N, M;
lint X, W, T;
LiChao li_chao(INF);
lint S[MAXN], P[MAXN];
pair<lint, lint> A[MAXN];

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  X = ReadInt();
  N = ReadInt();
  M = ReadInt();
  W = ReadInt();
  T = ReadInt();

  for (int i = 0; i < N; i++) {
    S[i] = ReadInt();
  }
  S[N] = X;
  vector<int> order(N + 1);
  iota(begin(order), end(order), 0);
  sort(begin(order), end(order), [&](int i, int j) {
    return (S[i] % T) < (S[j] % T);
  });

  for (int i = 0; i < M; i++) {
    A[i].first = ReadInt();
    A[i].second = ReadInt();
  }
  sort(A, A + M);
  for (int i = 0; i < M; i++) {
    P[i + 1] = P[i] + A[i].second;
  }

  // At time t1 delete [a, b].
  // At time t2 delete [c, d].
  // Then [a, b] and [c, d] will never overlap in optimal answer.
  // If they overlap, we can delete the overlapping region at min(t1, t2) to get more benefit.
  // This is possible since we can keep extending both a and b to the left until 0.

  vector<lint> dp(M + 1, INF);
  dp[0] = (X + T - 1) / T * W;
  for (int i = 0, ptr = 0; i < M; i++) {
    chmin(dp[i + 1], dp[i] + (X + T - 1 - A[i].first) / T * W);
    li_chao.InsertLine(0, INF - 1, Line(-i, dp[i] - P[i]));
    while (ptr <= N) {
      int p = upper_bound(A, A + M, make_pair(S[order[ptr]] % T, (__int128_t) -1)) - A;
      if (p < i + 1) {
        ptr += 1;
        continue;
      }
      if (p == i + 1) {
        lint x = S[order[ptr]] / T * W;
        chmin(dp[i + 1], (i + 1) * x + P[i + 1] + li_chao.Query(x));
        ptr += 1;
      } else {
        break;
      }
    }
  }

  Write(dp[M]);
  return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 30 / 30
• Subtask 3: 25 / 25
• Subtask 4: 29 / 29