Submission #963738

#	Time	Username	Problem	Language	Result	Execution time	Memory
963738		Soumya1	Treatment Project (JOI20_treatment)	C++17	100 / 100	326 ms	34924 KiB

treatment

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e18;
const int l2 = 2e9 + 10;
struct SegmentTree {
  int n;
  vector<pair<int, int>> t;
  vector<multiset<pair<int, int>>> mst;
  SegmentTree(int _n) {
    n = _n;
    t.assign(4 * n, {l2, l2});
    mst.resize(n + 1);
  }
  void update(int x, int lx, int rx, int i, pair<int, int> v, bool erase) {
    if (lx == rx) {
      if (erase) mst[lx].erase(mst[lx].find(v));
      else mst[lx].insert(v);
      if (mst[lx].empty()) t[x] = {l2, l2};
      else t[x] = *mst[lx].begin();
      return;
    }
    int mx = (lx + rx) >> 1;
    if (i <= mx) update(x << 1, lx, mx, i, v, erase);
    else update(x << 1 | 1, mx + 1, rx, i, v, erase);
    t[x] = min(t[x << 1], t[x << 1 | 1]);
  }
  pair<int, int> query(int x, int lx, int rx, int l, int r) {
    if (l > rx || lx > r || l > r) return {l2, l2};
    if (l <= lx && r >= rx) return t[x];
    int mx = (lx + rx) >> 1;
    return min(query(x << 1, lx, mx, l, r), query(x << 1 | 1, mx + 1, rx, l, r));
  }
};
void testCase() {
  int n, m;
  cin >> n >> m;
  vector<int> t(m), l(m), r(m), c(m), all, tt(m);
  for (int i = 0; i < m; i++) {
    cin >> t[i] >> l[i] >> r[i] >> c[i];
    all.push_back(t[i]);
  }
  sort(all.begin(), all.end());
  for (int i = 0; i < m; i++) {
    tt[i] = lower_bound(all.begin(), all.end(), t[i]) - all.begin() + 1;
  }
  SegmentTree st1(m), st2(m);
  for (int i = 0; i < m; i++) {
    st1.update(1, 1, m, tt[i], {l[i] - t[i], i}, false);
    st2.update(1, 1, m, tt[i], {l[i] + t[i], i}, false);
  }
  priority_queue<pair<ll, int>> pq;
  vector<bool> vis(m);
  vector<ll> dist(m, inf);
  for (int i = 0; i < m; i++) {
    if (l[i] == 1) {
      st1.update(1, 1, m, tt[i], {l[i] - t[i], i}, true);
      st2.update(1, 1, m, tt[i], {l[i] + t[i], i}, true);
      dist[i] = c[i];
      pq.push({-dist[i], i});
    }
  }
  while (!pq.empty()) {
    auto [_, u] = pq.top();
    pq.pop();
    if (vis[u]) continue;
    vis[u] = true;
    auto q = st1.query(1, 1, m, 1, tt[u]);
    while (q.first <= r[u] - t[u] + 1) {
      auto [v, i] = q;
      st1.update(1, 1, m, tt[i], {l[i] - t[i], i}, true);
      st2.update(1, 1, m, tt[i], {l[i] + t[i], i}, true);
      dist[i] = dist[u] + c[i];
      pq.push({-dist[i], i});
      q = st1.query(1, 1, m, 1, tt[u]);
    }
    q = st2.query(1, 1, m, tt[u], m);
    while (q.first <= r[u] + t[u] + 1) {
      auto [v, i] = q;
      st1.update(1, 1, m, tt[i], {l[i] - t[i], i}, true);
      st2.update(1, 1, m, tt[i], {l[i] + t[i], i}, true);
      dist[i] = dist[u] + c[i];
      pq.push({-dist[i], i});
      q = st2.query(1, 1, m, tt[u], m);
    }
  }
  ll ans = inf;
  for (int i = 0; i < m; i++) {
    if (r[i] == n) ans = min(ans, dist[i]);
  }
  cout << (ans == inf ? -1 : ans) << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  return 0;
}

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