Submission #220279

#	Time	Username	Problem	Language	Result	Execution time	Memory
220279		fedoseevtimofey	Treatment Project (JOI20_treatment)	C++14	100 / 100	232 ms	17904 KiB

treatment

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>
 
using namespace std;
 
typedef long long ll;
 
const ll Inf = 1e18;

struct Node {
  int val, id;
  Node(int val, int id) : val(val), id(id) {}
  Node() : val((int)2e9), id(-1) {}
  Node operator +(const Node &other) const {
    if (val <= other.val) return (*this);
    else return other;
  } 
};

const int N = 2e5 + 7;

Node t[4 * N];

void build(int l, int r, int v, vector <int> &a) {
  if (l == r) {
    t[v] = Node(a[l], l);
  } else {
    int m = (l + r) >> 1;
    build(l, m, 2 * v + 1, a);
    build(m + 1, r, 2 * v + 2, a);
    t[v] = t[2 * v + 1] + t[2 * v + 2];
  }
}

Node get(int ql, int qr, int l, int r, int v) {
  if (qr < l || r < ql) return Node();
  if (ql <= l && r <= qr) return t[v];
  int m = (l + r) >> 1;
  return get(ql, qr, l, m, 2 * v + 1) + get(ql, qr, m + 1, r, 2 * v + 2);
}

void kill(int id, int l, int r, int v) {
  if (l == r) {
    t[v] = Node(); 
  } else {
    int m = (l + r) >> 1;
    if (id <= m) kill(id, l, m, 2 * v + 1);
    else kill(id, m + 1, r, 2 * v + 2);
    t[v] = t[2 * v + 1] + t[2 * v + 2];
  } 
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int n, m;
  cin >> n >> m;
  vector <int> t(m), l(m), r(m), c(m);
  vector <pair <int, int>> cm;
  for (int i = 0; i < m; ++i) {
    cin >> t[i] >> l[i] >> r[i] >> c[i];
    --l[i];
    cm.push_back({l[i] + t[i], i});
  }
  sort(cm.begin(), cm.end());
  vector <int> a(m);
  vector <int> pos(m);
  for (int i = 0; i < m; ++i) {
    int id = cm[i].second;
    a[i] = l[id] - t[id];
    pos[id] = i;
  }
  build(0, m - 1, 0, a);
  // r[i] - t[i] >= l[j] - t[j]
  // r[i] + t[i] >= l[j] + t[j]
  // i -> j
  set <pair <ll, int>> q;
  for (int i = 0; i < m; ++i) {
    if (l[i] == 0) {
      q.insert({c[i], i});
      kill(pos[i], 0, m - 1, 0);
    }
  }
  ll ans = Inf;
  while (!q.empty()) {
    auto p = *q.begin();
    q.erase(q.begin());
    int u = p.second;
    ll cd = p.first;
    if (r[u] == n) ans = min(ans, cd);
    int cr = upper_bound(cm.begin(), cm.end(), make_pair(r[u] + t[u], n)) - cm.begin() - 1;
    while (true) {
      auto nd = get(0, cr, 0, m - 1, 0);
      if (nd.val <= r[u] - t[u]) {
        int v = cm[nd.id].second;
        kill(pos[v], 0, m - 1, 0);
        q.insert({cd + c[v], v});
      } else {
        break;
      }
    }
  }
  if (ans == Inf) cout << "-1\n";
  else cout << ans << '\n';
}

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