Submission #492549

#	Time	Username	Problem	Language	Result	Execution time	Memory
492549		Alex_tz307	Treatment Project (JOI20_treatment)	C++17	100 / 100	211 ms	14068 KiB

treatment

#include <bits/stdc++.h>

using namespace std;

const int kM = 1e5;
const int INF = 2e9 + 1;
const pair<int, int> pINF = {INF, INF};
const int64_t INFL = 1e18L;
int t[1 + kM], tt[1 + kM], l[1 + kM], r[1 + kM], c[1 + kM];
pair<int, int> a[1 + kM];
int64_t dp[1 + kM];

struct ST {
  int n;
  vector<pair<int, int>> t;

  ST(int N) : n(N) {
    int dim = 1;
    while (dim < n) {
      dim <<= 1;
    }
    t.resize(dim << 1, pINF);
  }

  void update(int x, int lx, int rx, int pos, pair<int, int> v) {
    if (lx == rx) {
      t[x] = v;
      return;
    }
    int mid = (lx + rx) >> 1;
    if (pos <= mid) {
      update(x << 1, lx, mid, pos, v);
    } else {
      update(x << 1 | 1, mid + 1, rx, pos, v);
    }
    t[x] = min(t[x << 1], t[x << 1 | 1]);
  }

  void update(int pos, pair<int, int> v) {
    update(1, 1, n, pos, v);
  }

  pair<int, int> query(int x, int lx, int rx, int st, int dr) {
    if (st <= lx && rx <= dr) {
      return t[x];
    }
    int mid = (lx + rx) >> 1;
    pair<int, int> ans1 = pINF, ans2 = pINF;
    if (st <= mid) {
      ans1 = query(x << 1, lx, mid, st, dr);
    }
    if (mid + 1 <= dr) {
      ans2 = query(x << 1 | 1, mid + 1, rx, st, dr);
    }
    return min(ans1, ans2);
  }

  pair<int, int> query(int st, int dr) {
    return query(1, 1, n, st, dr);
  }
};

void testCase() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    cin >> t[i] >> l[i] >> r[i] >> c[i];
    ++r[i];
    a[i] = make_pair(t[i], i);
  }
  sort(a + 1, a + m + 1);
  for (int i = 1; i <= m; ++i) {
    tt[a[i].second] = i;
  }
  priority_queue<pair<int64_t, int>, vector<pair<int64_t, int>>, greater<pair<int64_t, int>>> pq;
  ST t1(m), t2(m);
  for (int i = 1; i <= m; ++i) {
    dp[i] = INFL;
    if (l[i] == 1) {
      dp[i] = c[i];
      pq.emplace(dp[i], i);
    } else {
      t1.update(tt[i], {l[i] - t[i], i});
      t2.update(tt[i], {l[i] + t[i], i});
    }
  }
  while (!pq.empty()) {
    int u = pq.top().second;
    pq.pop();
    int v = t1.query(1, tt[u]).second;
    while (v != INF && l[v] - t[v] <= r[u] - t[u]) {
      t1.update(tt[v], pINF);
      t2.update(tt[v], pINF);
      pq.emplace(dp[v] = dp[u] + c[v], v);
      v = t1.query(1, tt[u]).second;
    }
    v = t2.query(tt[u], m).second;
    while (v != INF && l[v] + t[v] <= r[u] + t[u]) {
      t1.update(tt[v], pINF);
      t2.update(tt[v], pINF);
      pq.emplace(dp[v] = dp[u] + c[v], v);
      v = t2.query(tt[u], m).second;
    }
  }
  int64_t ans = INFL;
  for (int i = 1; i <= m; ++i) {
    if (r[i] == n + 1) {
      ans = min(ans, dp[i]);
    }
  }
  if (ans == INFL) {
    cout << "-1\n";
  } else {
    cout << ans << '\n';
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

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