Submission #28300315

---

Source Code Expand

/*
 * Author: nskybytskyi
 * Time:   2022-01-02 17:42:09
 */

#include <bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int n, q;
  cin >> n >> q;

  vector<tuple<int, int, int>> stx(n);
  for (auto& [s, t, x] : stx) {
    cin >> s >> t >> x;
  }

  vector<pair<int, int>> d(q);
  for (int i = 0; i < q; ++i) {
    int di;
    cin >> di;
    di *= 2;
    d[i] = {di, i};
  }

  sort(d.begin(), d.end());

  vector<tuple<int, bool, int>> events;
  for (auto [s, t, x] : stx) {
    events.emplace_back((2 * s - 1) - 2 * x, true, x);
    events.emplace_back((2 * t - 1) - 2 * x, false, x);
  }

  sort(events.begin(), events.end());

  int j = 0;
  multiset<int> active;
  vector<int> ans(q, -1);

  for (auto [di, i] : d) {
    while (j < (n << 1) && get<0>(events[j]) < di) {
      const auto x = get<2>(events[j]);
      if (get<1>(events[j])) {
        active.insert(x);
      } else {
        active.erase(active.find(x));
      }
      ++j;
    }
    if (!active.empty()) {
      ans[i] = *active.begin();
    }
  }

  for (auto elem : ans) {
    cout << elem << "\n";
  }

  return 0;
}

Submission Info

Judge Result