Submission #882494

#	Time	Username	Problem	Language	Result	Execution time	Memory
882494		MilosMilutinovic	Treatment Project (JOI20_treatment)	C++14	100 / 100	528 ms	91340 KiB

treatment

#include <bits/stdc++.h>

using namespace std;

const int N = 4e5;

const int M = 4 * N;

set<pair<int, int>> all[2][N];

struct node {
  pair<int, int> mn;
  pair<int, int> mx;
} st[2][M];

node comb(node a, node b) {
  node res;
  res.mn = min(a.mn, b.mn);
  res.mx = max(a.mx, b.mx);
  return res;
}

void Build(int t, int x, int l, int r) {
  st[t][x].mn = {1.00001e9, -1};
  st[t][x].mx = {-1.00001e9, -1};
  if (l == r) {
    return;
  }
  int mid = l + r >> 1;
  Build(t, x * 2, l, mid);
  Build(t, x * 2 + 1, mid + 1, r);
}

void Modify(int t, int x, int l, int r, int p, pair<int, int> v) {
  if (l == r) {
    all[t][l].insert(v);
    st[t][x].mn = *all[t][l].begin();
    st[t][x].mx = *prev(all[t][l].end());
    return;
  }
  int mid = l + r >> 1;
  if (p <= mid) {
    Modify(t, x * 2, l, mid, p, v);
  } else {
    Modify(t, x * 2 + 1, mid + 1, r, p, v);
  }
  st[t][x] = comb(st[t][x * 2], st[t][x * 2 + 1]);
}

void Remove(int t, int x, int l, int r, int p, pair<int, int> v) {
  if (l == r) {
    all[t][l].erase(all[t][l].find(v));
    if (all[t][l].empty()) {
      st[t][x].mn = {1.00001e9, -1};
      st[t][x].mx = {-1.00001e9, -1};
    } else {
      st[t][x].mn = *all[t][l].begin();
      st[t][x].mx = *prev(all[t][l].end());
    }
    return;
  }
  int mid = l + r >> 1;
  if (p <= mid) {
    Remove(t, x * 2, l, mid, p, v);
  } else {
    Remove(t, x * 2 + 1, mid + 1, r, p, v);
  }
  st[t][x] = comb(st[t][x * 2], st[t][x * 2 + 1]);
}

node Query(int t, int x, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) {
    return st[t][x];
  }
  int mid = l + r >> 1;
  if (qr <= mid) {
    return Query(t, x * 2, l, mid, ql, qr);
  } else if (ql > mid) {
    return Query(t, x * 2 + 1, mid + 1, r, ql, qr);
  } else {
    return comb(Query(t, x * 2, l, mid, ql, qr), Query(t, x * 2 + 1, mid + 1, r, ql, qr));
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> t(m), l(m), r(m), c(m);
  for (int i = 0; i < m; i++) {
    cin >> t[i] >> l[i] >> r[i] >> c[i];
    --l[i];
  }
  vector<int> xs;
  for (int i = 0; i < m; i++) {
    xs.push_back(l[i] - t[i]);
    xs.push_back(l[i] + t[i]);
    xs.push_back(r[i] - t[i]);
    xs.push_back(r[i] + t[i]);
  }
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  auto GetVal = [&](int x) {
    return (int) (lower_bound(xs.begin(), xs.end(), x) - xs.begin());
  };
  int k = (int) xs.size();
  Build(0, 1, 0, k - 1);
  Build(1, 1, 0, k - 1);
  for (int i = 0; i < m; i++) {
    Modify(0, 1, 0, k - 1, GetVal(l[i] - t[i]), {t[i], i});
    Modify(1, 1, 0, k - 1, GetVal(l[i] + t[i]), {t[i], i});
  }
  const long long inf = (long long) 1e18;
  vector<long long> dist(m, inf);
  set<pair<long long, int>> st;
  for (int i = 0; i < m; i++) {
    if (l[i] == 0) {
      dist[i] = c[i];
      st.emplace(dist[i], i);
      Remove(0, 1, 0, k - 1, GetVal(l[i] - t[i]), {t[i], i});
      Remove(1, 1, 0, k - 1, GetVal(l[i] + t[i]), {t[i], i});
    }
  }
  while (!st.empty()) {
    auto it = st.begin();
    int i = it->second;
    st.erase(it);
    while (true) {
      {
        node nd = Query(0, 1, 0, k - 1, 0, GetVal(r[i] - t[i]));
        if (nd.mn.first <= t[i]) {
          int j = nd.mn.second;
          dist[j] = dist[i] + c[j];
          Remove(0, 1, 0, k - 1, GetVal(l[j] - t[j]), {t[j], j});
          Remove(1, 1, 0, k - 1, GetVal(l[j] + t[j]), {t[j], j});
          st.emplace(dist[j], j);
          continue;
        }
      }
      {
        node nd = Query(1, 1, 0, k - 1, 0, GetVal(r[i] + t[i]));
        if (nd.mx.first >= t[i]) {
          int j = nd.mx.second;
          dist[j] = dist[i] + c[j];
          Remove(0, 1, 0, k - 1, GetVal(l[j] - t[j]), {t[j], j});
          Remove(1, 1, 0, k - 1, GetVal(l[j] + t[j]), {t[j], j});
          st.emplace(dist[j], j);
          continue;
        }
      }
      break;
    }
  }
  long long res = inf;
  for (int i = 0; i < m; i++) {
    if (r[i] == n) {
      res = min(res, dist[i]);
    }
  }
  cout << (res == inf ? -1 : res) << '\n';
  return 0;
}

Compilation message (stderr)

treatment.cpp: In function 'void Build(int, int, int, int)':
treatment.cpp:29:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |   int mid = l + r >> 1;
      |             ~~^~~
treatment.cpp: In function 'void Modify(int, int, int, int, int, std::pair<int, int>)':
treatment.cpp:41:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |   int mid = l + r >> 1;
      |             ~~^~~
treatment.cpp: In function 'void Remove(int, int, int, int, int, std::pair<int, int>)':
treatment.cpp:62:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |   int mid = l + r >> 1;
      |             ~~^~~
treatment.cpp: In function 'node Query(int, int, int, int, int, int)':
treatment.cpp:75:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |   int mid = l + r >> 1;
      |             ~~^~~

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