Submission #1043148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043148		juicy	Treatment Project (JOI20_treatment)	C++17	100 / 100	146 ms	26960 KiB

treatment

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int M = 1e5 + 5, MAX = 2e9 + 2;
const long long inf = 1e18;

int n, m, k;
int t[M], l[M], r[M], c[M], pos[M];
array<int, 2> A[4 * M], B[4 * M];
bool del[M];
long long d[M];
vector<array<int, 2>> pf[M], sf[M];

void upd(vector<array<int, 2>> &cands) {
  while (cands.size() > 1 && del[cands.back()[1]]) {
    cands.pop_back();
  }
}

void pul(int id) {
  A[id] = min(A[id * 2], A[id * 2 + 1]);
  B[id] = min(B[id * 2], B[id * 2 + 1]);
}

void bld(int id = 1, int l = 1, int r = k) {
  if (l == r) {
    A[id] = pf[l].back();
    B[id] = sf[l].back();
    return;
  }
  int md = (l + r) / 2;
  bld(id * 2, l, md);
  bld(id * 2 + 1, md + 1, r);
  pul(id);
}

void ers(int i, int id = 1, int l = 1, int r = k) {
  if (l == r) {
    upd(pf[i]);
    upd(sf[i]);
    A[id] = pf[i].back();
    B[id] = sf[i].back();
    return;
  }
  int md = (l + r) / 2;
  if (i <= md) {
    ers(i, id * 2, l, md);
  } else {
    ers(i, id * 2 + 1, md + 1, r);
  }
  pul(id);
}

array<int, 2> qry(int u, int v, array<int, 2> *s, int id = 1, int l = 1, int r = k) {
  if (u <= l && r <= v) {
    return s[id];
  }
  int md = (l + r) / 2;
  if (v <= md) {
    return qry(u, v, s, id * 2, l, md);
  }
  if (md < u) {
    return qry(u, v, s, id * 2 + 1, md + 1, r);
  }
  return min(qry(u, v, s, id * 2, l, md), qry(u, v, s, id * 2 + 1, md + 1, r));
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> m;
  vector<int> comp;
  for (int i = 1; i <= m; ++i) {
    cin >> t[i] >> l[i] >> r[i] >> c[i];
    comp.push_back(t[i]);
  } 
  sort(comp.begin(), comp.end());
  comp.erase(unique(comp.begin(), comp.end()), comp.end());
  k = comp.size();
  for (int i = 1; i <= m; ++i) {
    pos[i] = lower_bound(comp.begin(), comp.end(), t[i]) - comp.begin() + 1;
    pf[pos[i]].push_back({l[i] - t[i], i});
    sf[pos[i]].push_back({l[i] + t[i], i});
  }
  for (int i = 1; i <= k; ++i) {
    pf[i].push_back({MAX, -1});
    sf[i].push_back({MAX, -1});
    sort(pf[i].rbegin(), pf[i].rend());
    sort(sf[i].rbegin(), sf[i].rend());
  }
  using T = pair<long long, int>;
  priority_queue<T, vector<T>, greater<T>> pq;
  bld();;
  fill(d + 1, d + m + 1, inf);
  for (int i = 1; i <= m; ++i) {
    if (l[i] == 1) {
      del[i] = 1;
      ers(pos[i]);
      pq.push({d[i] = c[i], i});
    }
  }
  while (pq.size()) {
    auto [x, u] = pq.top(); pq.pop();
    if (x != d[u]) {
      continue;
    }
    while (1) {
      auto dat = qry(1, pos[u], A);
      if (dat[0] > r[u] - t[u] + 1) {
        break;
      }
      int v = dat[1];
      pq.push({d[v] = x + c[v], v});
      del[v] = 1;
      ers(pos[v]);
    }
    while (1) {
      auto dat = qry(pos[u], k, B);
      if (dat[0] > r[u] + t[u] + 1) {
        break;
      }
      int v = dat[1];
      pq.push({d[v] = x + c[v], v});
      del[v] = 1;
      ers(pos[v]);
    }
  } 
  auto res = inf;
  for (int i = 1; i <= m; ++i) {
    if (r[i] == n) {
      res = min(res, d[i]);
    }
  }
  cout << (res == inf ? -1 : res);
  return 0;
}

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