Submission #217171

#	Time	Username	Problem	Language	Result	Execution time	Memory
217171		rama_pang	Treatment Project (JOI20_treatment)	C++14	100 / 100	256 ms	15420 KiB

treatment

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

class TreatmentProject {
 
 private:
  
  template<typename T> using min_queue = priority_queue<T, vector<T>, greater<T>>;

  struct Project {
    int T, L, R, C;
    Project() {}
    Project(int T, int L, int R, int C) : T(T), L(L), R(R), C(C) {}
  };

  int N_, M_;
  vector<Project> project_;

  long long NaiveDijkstraDP() { // O(M^2) Dijsktra-DP solution (naive)
    int N = N_, M = M_;
    vector<Project> project = project_;
    
    assert(M <= 5000);

    for (int i = 0; i < M; i++) {
      project[i].R++;
    } // project[i] cures [L[i], R[i])


    vector<long long> dp(M, 1e18);
    vector<bool> vis(M, false);

    int current = -1;

    for (int i = 0; i < M; i++) {
      if (project[i].R > N) {
        dp[i] = project[i].C;
        if (current == -1 || dp[current] > dp[i]) {
          current = i;
        }
      }
    }

    while (current != -1) { // Dijkstra's Algorithm
      vis[current] = true;

      for (int now = 0; now < M; now++) {
        if (vis[now]) continue;

        bool CanTransition = false;
        if (project[now].T >= project[current].T) {
          CanTransition = project[now].R >= project[current].L + (project[now].T - project[current].T);
        } else {
          CanTransition = project[now].R - (project[current].T - project[now].T) >= project[current].L;
        }

        if (CanTransition) {
          dp[now] = min(dp[now], project[now].C + dp[current]);
        }
      }

      int nxt = -1;

      for (int now = 0; now < M; now++) {
        if (vis[now]) continue;
        if (nxt == -1 || dp[nxt] > dp[now]) {
          nxt = now;
        }
      }

      current = nxt;
    }

    long long res = 1e18;

    for (int i = 0; i < M; i++) {
      if (project[i].L == 1) {
        res = min(res, dp[i]);
      }
    }

    if (res == (long long) 1e18) { // no solution exists
      res = -1;
    }

    return res;
  }

  class RangeTree { // O(log^2 M) per operation
   
   private:

    class DisjointSet {
     
     private:

      int BASE = 5;
      vector<int> p;

      int Find_(int x) {
        return p[x] == x ? x : p[x] = Find_(p[x]);
      }

      bool Union_(int x, int y) { // p[x] = y
        x = Find_(x), y = Find_(y);
        if (x != y) {
          p[x] = y;
          return true;
        } else {
          return false;
        }
      }

     public:

      DisjointSet() {}

      void Init(int n) {
        p.resize(n + BASE + BASE);
        iota(begin(p), end(p), 0);
      }

      int Find(int x) {
        return Find_(x + BASE) - BASE;
      }

      bool Union(int x, int y) {
        return Union_(x + BASE, y + BASE);
      }

    };

    int sz;

    vector<vector<pair<int, int>>> tree; // sorted vector (time, index)
    vector<DisjointSet> dsu;

    int LowerBound(int n, pair<int, int> x) { // lower_bound on tree[n]
      int lo = 0, hi = tree[n].size();

      while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (mid >= 0 && tree[n][mid] >= x) {
          hi = mid;
        } else {
          lo = mid + 1;
        }
      }

      return dsu[n].Find(hi);
    }

    bool VectorErase(int n, pair<int, int> x) {
      int pos = LowerBound(n, x);
      if (pos < tree[n].size() && tree[n][pos] == x) {
        dsu[n].Union(pos, pos + 1);
        return true;
      } else {
        return false;
      }
    }

    vector<Project> project;
    vector<pair<int, int>> base;

    void Pull(int n) {
      dsu[n].Init(tree[n * 2].size() + tree[n * 2 + 1].size());
      tree[n].resize(tree[n * 2].size() + tree[n * 2 + 1].size());
      merge(begin(tree[n * 2]), end(tree[n * 2]), begin(tree[n * 2 + 1]), end(tree[n * 2 + 1]), begin(tree[n]));
    }

    void Build(int n, int tl, int tr, const vector<pair<int, int>> &a) { // tree = (time, index)
      if (tl == tr) {
        dsu[n].Init(1);
        tree[n].emplace_back(make_pair(project[a[tl].second].T, a[tl].second));
        return;
      }
      int mid = (tl + tr) / 2;
      Build(n * 2, tl, mid, a);
      Build(n * 2 + 1, mid + 1, tr, a);
      Pull(n);
    }

    void Erase(int n, int tl, int tr, const pair<int, int> &a) { // element a to be deleted from segment tree
      if (!VectorErase(n, a)) return;
      if (tl == tr) return;
      int mid = (tl + tr) / 2;
      Erase(n * 2, tl, mid, a);
      Erase(n * 2 + 1, mid + 1, tr, a);
    }

    void Query(int n, int tl, int tr, int l, int r, int t1, int t2, vector<int> &res) {
      if (tr < l || r < tl || tl > tr || l > r) return;
      if (l <= tl && tr <= r) {
        int pos = LowerBound(n, make_pair(t1, INT_MIN));
        while (pos < tree[n].size()) {
          if (tree[n][pos].first > t2) break;
          assert(t1 <= tree[n][pos].first && tree[n][pos].first <= t2);
          res.emplace_back(tree[n][pos].second);
          pos = dsu[n].Find(pos + 1);
        }
        return;
      }
      int mid = (tl + tr) / 2;
      Query(n * 2, tl, mid, l, r, t1, t2, res);
      Query(n * 2 + 1, mid + 1, tr, l, r, t1, t2, res);
    }

   public:

    RangeTree(int n, const vector<Project> &proj) {
      sz = n;
      project = proj;
      tree.resize(4 * n);
      dsu.resize(4 * n);
    }

    void Build(const vector<pair<int, int>> &a) {
      base = a;
      return Build(1, 0, sz - 1, a);
    }

    void Erase(int x) {
      return Erase(1, 0, sz - 1, pair<int, int>(project[x].T, x));
    }

    void Query(int l, int r, int t1, int t2, vector<int> &res) { // get ids from segment [l, r] with time <= t, and place it into res
      l = lower_bound(begin(base), end(base), make_pair(l, INT_MIN)) - begin(base);
      r = upper_bound(begin(base), end(base), make_pair(r, INT_MAX)) - begin(base) - 1;
      
      return Query(1, 0, sz - 1, l, r, t1, t2, res);
    }

  };

  long long RangeTreeDijkstraDP() { // O(M log^2 M) Dijkstra-DP solution (optimized with RangeTree)
    int N = N_, M = M_;
    vector<Project> project = project_;
 
    for (int i = 0; i < M; i++) {
      project[i].R++;
    }
 
    RangeTree RMinusT(M, project), RPlusT(M, project);
 
    { // Initialize RMinusT (base sorted by R[i] - T[i])
      vector<pair<Project, int>> a;
      for (int i = 0; i < M; i++) {
        a.emplace_back(project[i], i);
      }
 
      sort(begin(a), end(a), [&](const pair<Project, int> &a, const pair<Project, int> &b) {
        return a.first.R - a.first.T < b.first.R - b.first.T;
      });
 
      vector<pair<int, int>> base; // (R - T, index)
      for (auto &i : a) {
        base.emplace_back(i.first.R - i.first.T, i.second);
      }
 
      RMinusT.Build(base);
    }
 
    { // Initialize RPlusT (base sorted by R[i] + T[i])
      vector<pair<Project, int>> a;
      for (int i = 0; i < M; i++) {
        a.emplace_back(project[i], i);
      }
 
      sort(begin(a), end(a), [&](const pair<Project, int> &a, const pair<Project, int> &b) {
        return a.first.R + a.first.T < b.first.R + b.first.T;
      });
 
      vector<pair<int, int>> base; // (R + T, index)
      for (auto &i : a) {
        base.emplace_back(i.first.R + i.first.T, i.second);
      }
 
      RPlusT.Build(base);
    }
 
    min_queue<pair<long long, int>> pq;
    vector<long long> dp(M, 1e18);
    for (int i = 0; i < M; i++) {
      if (project[i].R > N) {
        dp[i] = project[i].C;
        pq.emplace(dp[i], i);
        RMinusT.Erase(i);
        RPlusT.Erase(i);
      }
    }
 
    while (!pq.empty()) {
      int cur = pq.top().second;
      pq.pop();
 
      vector<int> candidates;
      RMinusT.Query(project[cur].L - project[cur].T, INT_MAX, project[cur].T, INT_MAX, candidates);
      RPlusT.Query(project[cur].L + project[cur].T, INT_MAX, 1, project[cur].T, candidates);
      
      sort(begin(candidates), end(candidates));
      candidates.resize(unique(begin(candidates), end(candidates)) - begin(candidates));
 
      for (auto &i : candidates) {
        dp[i] = project[i].C + dp[cur];
        pq.emplace(dp[i], i);
 
        RMinusT.Erase(i);
        RPlusT.Erase(i);
      }
    }
 
    long long res = 1e18;
 
    for (int i = 0; i < M; i++) {
      if (project[i].L == 1) {
        res = min(res, dp[i]);
      }
    }
 
    if (res == (long long) 1e18) {
      res = -1;
    }
 
    return res;
  }
 
  class SegmentTree { // O(log M) per operation
   private:

    int sz;

    vector<pair<int, int>> tree_max; // (time, index), sorted by R - T
    vector<pair<int, int>> tree_min; // (time, index), sorted by R + T
    
    vector<Project> project;
    vector<pair<int, int>> base_max;
    vector<pair<int, int>> base_min;
    vector<int> reverse_max;
    vector<int> reverse_min;

   public:

    SegmentTree(int n, const vector<Project> &p) {
      sz = n;
      project = p;
      tree_max.assign(2 * sz, {-1, -1});
      tree_min.assign(2 * sz, {INT_MAX, -1});
    }

    void BuildMax(const vector<pair<int, int>> &a) {
      base_max = a;
      reverse_max.resize(a.size());
      for (int i = 0; i < a.size(); i++) {
        tree_max[i + sz] = make_pair(project[a[i].second].T, a[i].second);
        reverse_max[a[i].second] = i;
      }
      for (int i = sz - 1; i > 0; i--) {
        tree_max[i] = max(tree_max[i * 2], tree_max[i * 2 + 1]);
      }
    }

    void BuildMin(const vector<pair<int, int>> &a) {
      base_min = a;
      reverse_min.resize(a.size());
      for (int i = 0; i < a.size(); i++) {
        tree_min[i + sz] = make_pair(project[a[i].second].T, a[i].second);
        reverse_min[a[i].second] = i;
      }
      for (int i = sz - 1; i > 0; i--) {
        tree_min[i] = min(tree_min[i * 2], tree_min[i * 2 + 1]);
      }
    }

    int QueryMax(int l, int r, int t) { // suffix t...inf
      l = lower_bound(begin(base_max), end(base_max), make_pair(l, INT_MIN)) - begin(base_max);
      r = upper_bound(begin(base_max), end(base_max), make_pair(r, INT_MAX)) - begin(base_max) - 1;
      
      pair<int, int> res = {-1, -1};
      for (l += sz, r += sz + 1; l < r; l /= 2, r /= 2) {
        if (l & 1) res = max(res, tree_max[l++]);
        if (r & 1) res = max(res, tree_max[--r]);
      }

      return res.first < t ? -1 : res.second;
    }

    int QueryMin(int l, int r, int t) { // prefix 1...t
      l = lower_bound(begin(base_min), end(base_min), make_pair(l, INT_MIN)) - begin(base_min);
      r = upper_bound(begin(base_min), end(base_min), make_pair(r, INT_MAX)) - begin(base_min) - 1;
      
      pair<int, int> res = {INT_MAX, -1};
      for (l += sz, r += sz + 1; l < r; l /= 2, r /= 2) {
        if (l & 1) res = min(res, tree_min[l++]);
        if (r & 1) res = min(res, tree_min[--r]);
      }
      return res.first > t ? -1 : res.second;
    }
    
    void EraseMax(int id) {
      id = reverse_max[id];
      tree_max[id += sz] = {-1, -1};
      for (id /= 2; id > 0; id /= 2) {
        tree_max[id] = max(tree_max[id * 2], tree_max[id * 2 + 1]);
      }
    }

    void EraseMin(int id) {
      id = reverse_min[id];
      tree_min[id += sz] = {INT_MAX, -1};
      for (id /= 2; id > 0; id /= 2) {
        tree_min[id] = min(tree_min[id * 2], tree_min[id * 2 + 1]);
      }
    }

  };

  long long SegmentTreeDijkstraDP() { // O(M log M) Dijkstra-DP solution (optimized with SegmentTree)
    int N = N_, M = M_;
    vector<Project> project = project_;

    for (int i = 0; i < M; i++) {
      project[i].R++;
    }

    SegmentTree SegTree(M, project);
    // RangeTree RMinusT(M, project), RPlusT(M, project); // O(log^2 M) per operation

    { // Initialize RMinusT (base sorted by R[i] - T[i])
      vector<pair<Project, int>> a;
      for (int i = 0; i < M; i++) {
        a.emplace_back(project[i], i);
      }

      sort(begin(a), end(a), [&](const pair<Project, int> &a, const pair<Project, int> &b) {
        return a.first.R - a.first.T < b.first.R - b.first.T;
      });

      vector<pair<int, int>> base; // (R - T, index)
      for (auto &i : a) {
        base.emplace_back(i.first.R - i.first.T, i.second);
      }

      SegTree.BuildMax(base);
    }

    { // Initialize RPlusT (base sorted by R[i] + T[i])
      vector<pair<Project, int>> a;
      for (int i = 0; i < M; i++) {
        a.emplace_back(project[i], i);
      }

      sort(begin(a), end(a), [&](const pair<Project, int> &a, const pair<Project, int> &b) {
        return a.first.R + a.first.T < b.first.R + b.first.T;
      });

      vector<pair<int, int>> base; // (R + T, index)
      for (auto &i : a) {
        base.emplace_back(i.first.R + i.first.T, i.second);
      }

      SegTree.BuildMin(base);
    }

    min_queue<pair<long long, int>> pq;
    vector<long long> dp(M, 1e18);
    for (int i = 0; i < M; i++) {
      if (project[i].R > N) {
        dp[i] = project[i].C;
        pq.emplace(dp[i], i);
        SegTree.EraseMax(i);
        SegTree.EraseMin(i);
      }
    }

    while (!pq.empty()) {
      int cur = pq.top().second;
      pq.pop();

      vector<int> candidates;

      while (true) { // get ids which satisfies R - T constraints
        int now = SegTree.QueryMax(project[cur].L - project[cur].T, INT_MAX, project[cur].T);
        if (now == -1) break;

        SegTree.EraseMax(now);
        SegTree.EraseMin(now);
        candidates.emplace_back(now);
      }

      while (true) { // get ids which satisfies R + T constraints
        int now = SegTree.QueryMin(project[cur].L + project[cur].T, INT_MAX, project[cur].T);
        if (now == -1) break;

        SegTree.EraseMax(now);
        SegTree.EraseMin(now);
        candidates.emplace_back(now);
      }

      for (auto &i : candidates) {
        dp[i] = project[i].C + dp[cur];
        pq.emplace(dp[i], i);
      }
    }

    long long res = 1e18;

    for (int i = 0; i < M; i++) {
      if (project[i].L == 1) {
        res = min(res, dp[i]);
      }
    }

    if (res == (long long) 1e18) {
      res = -1;
    }

    return res;
  }

 public:

  void Read() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> N_ >> M_;
    for (int i = 0; i < M_; i++) {
      int T, L, R, C;
      cin >> T >> L >> R >> C;
      project_.emplace_back(T, L, R, C);
    }
  }

  long long Solve() {
    return SegmentTreeDijkstraDP();
  }

};

int main() {
  TreatmentProject Solver;
  Solver.Read();
  cout << Solver.Solve() << "\n";
  return 0;
}

Compilation message (stderr)

treatment.cpp: In member function 'bool TreatmentProject::RangeTree::VectorErase(int, std::pair<int, int>)':
treatment.cpp:155:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if (pos < tree[n].size() && tree[n][pos] == x) {
           ~~~~^~~~~~~~~~~~~~~~
treatment.cpp: In member function 'void TreatmentProject::RangeTree::Query(int, int, int, int, int, int, int, std::vector<int>&)':
treatment.cpp:196:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (pos < tree[n].size()) {
                ~~~~^~~~~~~~~~~~~~~~
treatment.cpp: In member function 'void TreatmentProject::SegmentTree::BuildMax(const std::vector<std::pair<int, int> >&)':
treatment.cpp:354:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < a.size(); i++) {
                       ~~^~~~~~~~~~
treatment.cpp: In member function 'void TreatmentProject::SegmentTree::BuildMin(const std::vector<std::pair<int, int> >&)':
treatment.cpp:366:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < a.size(); i++) {
                       ~~^~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 61 / 61