답안 #989063

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
989063	2024-05-27T11:35:13 Z	MilosMilutinovic	RMQ (NOI17_rmq)	C++14	컴파일 오류	0 ms	0 KB

rmq

#include <bits/stdc++.h>

using namespace std;

template <typename T, typename F>
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<vector<vector<int>>> qs(n, vector<vector<int>>(2));
  for (int i = 0; i < q; i++) {
    qs[l[i]][0].emplace_back(a[i]);
    qs[r[i]][1].emplace_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() ? n - 1 : *prev(st.end()));
    for (int v : qs[i][1]) {
      st.erase(st.find(v));
    }
  }
  SparseTable mn(bound, [&](int i, int j) { return min(i, j); });
  for (int i = 0; i < q; i++) {
    if (mn.get(l[i], r[i]) != a[i]) {
      bound = vector<int>(n, -1);
      break;
    }
  }
  for (int i = 0; i < n; i++) {
    cout << bound[i] << " ";
  }
  cout << '\n';
  return 0;
}

Compilation message

rmq.cpp: In function 'int main()':
rmq.cpp:59:15: error: missing template arguments before 'mn'
   59 |   SparseTable mn(bound, [&](int i, int j) { return min(i, j); });
      |               ^~
rmq.cpp:59:64: error: expected primary-expression before ')' token
   59 |   SparseTable mn(bound, [&](int i, int j) { return min(i, j); });
      |                                                                ^
rmq.cpp:61:9: error: 'mn' was not declared in this scope; did you mean 'n'?
   61 |     if (mn.get(l[i], r[i]) != a[i]) {
      |         ^~
      |         n