Submission #989088

#	Time	Username	Problem	Language	Result	Execution time	Memory
989088		MilosMilutinovic	RMQ (NOI17_rmq)	C++14	100 / 100	102 ms	32204 KiB

rmq

#include <bits/stdc++.h>

using namespace std;

template <typename T, class F = function<T(const T&, const T&)>>
class SparseTable {
 public:
  int n;
  vector<vector<T>> mat;
  F func;

  SparseTable(const vector<T>& a, const F& f) : func(f) {
    n = static_cast<int>(a.size());
    int max_log = 32 - __builtin_clz(n);
    mat.resize(max_log);
    mat[0] = a;
    for (int j = 1; j < max_log; j++) {
      mat[j].resize(n - (1 << j) + 1);
      for (int i = 0; i <= n - (1 << j); i++) {
        mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
      }
    }
  }

  T get(int from, int to) const {
    assert(0 <= from && from <= to && to <= n - 1);
    int lg = 32 - __builtin_clz(to - from + 1) - 1;
    return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  vector<int> l(q);
  vector<int> r(q);
  vector<int> a(q);
  for (int i = 0; i < q; i++) {
    cin >> l[i] >> r[i] >> a[i];
  }
  vector<int> L(n, 0), R(n, n - 1);
  vector<bool> was(n);
  for (int i = 0; i < q; i++) {
    L[a[i]] = max(L[a[i]], l[i]);
    R[a[i]] = min(R[a[i]], r[i]);
    was[a[i]] = true;
  }
  auto No = [&]() {
    for (int i = 0; i < n; i++) {
      cout << -1 << " ";
    }
    cout << '\n';
    exit(0);
  }; 
  for (int i = 0; i < n; i++) {
    if (L[i] > R[i]) {
      No();
    }
  }
  vector<vector<vector<int>>> qs(n, vector<vector<int>>(2));
  for (int i = 0; i < q; i++) {
    qs[l[i]][0].push_back(a[i]);
    qs[r[i]][1].push_back(a[i]);
  }
  vector<int> bound(n);
  multiset<int> st;
  for (int i = 0; i < n; i++) {
    for (int v : qs[i][0]) {
      st.insert(v);
    }
    bound[i] = (st.empty() ? 0 : *prev(st.end()));
    for (int v : qs[i][1]) {
      st.erase(st.find(v));
    }
  }
  SparseTable<int> mn(bound, [&](int i, int j) { return min(i, j); });
  for (int i = 0; i < n; i++) {
    if (!was[i]) {
      continue;
    }
    if (mn.get(L[i], R[i]) != i) {
      No();
    }
  }
  vector<set<int>> pos(n);
  for (int i = 0; i < n; i++) {
    pos[bound[i]].insert(i);
  }
  vector<int> res(n, -1);
  for (int i = 0; i < n; i++) {
    if (!was[i]) {
      continue;
    }
    auto it = pos[i].lower_bound(L[i]);
    if (it == pos[i].end() || *it > R[i]) {
      No();
    }
    res[*it] = i;
  }
  vector<int> order;
  for (int i = 0; i < n; i++) {
    if (res[i] == -1) {
      order.push_back(i);
    }
  }
  sort(order.begin(), order.end(), [&](int i, int j) {
    return bound[i] > bound[j];
  });
  int ptr = 0;
  for (int i = n - 1; i >= 0; i--) {
    if (was[i]) {
      continue;
    }
    res[order[ptr]] = i;
    ptr += 1;
  }
  mn = SparseTable<int>(res, [&](int i, int j) { return min(i, j); });
  for (int i = 0; i < q; i++) {
    if (mn.get(l[i], r[i]) != a[i]) {
      No();
    }
  }
  for (int i = 0; i < n; i++) {
    cout << res[i] << " ";
  }
  cout << '\n';
  return 0;
}

• Subtask 1: 23 / 23
• Subtask 2: 44 / 44
• Subtask 3: 33 / 33