Submission #282455

#	Time	Username	Problem	Language	Result	Execution time	Memory
282455		rama_pang	Long Distance Coach (JOI17_coach)	C++14	0 / 100	1 ms	384 KiB

coach

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

using lint = long long;
const lint INF = 2e18;
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); }

struct Line {
  lint a, b;
  Line() : a(0), b(INF) {}
  Line(lint a, lint b) : a(a), b(b) {}
  lint get(lint x) {
    if (double(a) * double(x) > INF) {
      return INF;
    }
    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) {}
  vector<Line> all;
  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);

  cin >> X >> N >> M >> W >> T;
  for (int i = 0; i < N; i++) {
    cin >> S[i];
  }
  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++) {
    cin >> A[i].first >> A[i].second;
  }
  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, -1ll)) - A;
      if (p < i + 1) {
        ptr += 1;
        continue;
      }
      if (p == i + 1) {
        lint x = S[order[ptr]] / T * W;
        if (double(i + 1) * double(x) <= INF) {
          chmin(dp[i + 1], (i + 1) * x + P[i + 1] + li_chao.Query(x));
        }
        ptr += 1;
      } else {
        break;
      }
    }
  }

  cout << dp[M] << "\n";
  return 0;
}

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