답안 #989067

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
989067	2024-05-27T11:42:18 Z	MilosMilutinovic	RMQ (NOI17_rmq)	C++14	30 / 100	84 ms	19576 KB

#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<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<int> 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;
}

Subtask #1
6.9 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	0 ms	344 KB	Output is partially correct
2	Partially correct	0 ms	348 KB	Output is partially correct
3	Partially correct	0 ms	348 KB	Output is partially correct
4	Partially correct	0 ms	348 KB	Output is partially correct
5	Partially correct	0 ms	348 KB	Output is partially correct
6	Correct	0 ms	452 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Partially correct	1 ms	348 KB	Output is partially correct

Subtask #2
13.2 / 44.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	0 ms	344 KB	Output is partially correct
2	Partially correct	0 ms	348 KB	Output is partially correct
3	Partially correct	0 ms	348 KB	Output is partially correct
4	Partially correct	0 ms	348 KB	Output is partially correct
5	Partially correct	0 ms	348 KB	Output is partially correct
6	Correct	0 ms	452 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Partially correct	1 ms	348 KB	Output is partially correct
12	Partially correct	1 ms	856 KB	Output is partially correct
13	Partially correct	1 ms	604 KB	Output is partially correct
14	Partially correct	1 ms	348 KB	Output is partially correct
15	Partially correct	1 ms	604 KB	Output is partially correct
16	Partially correct	1 ms	604 KB	Output is partially correct
17	Partially correct	1 ms	604 KB	Output is partially correct
18	Partially correct	1 ms	348 KB	Output is partially correct
19	Partially correct	1 ms	348 KB	Output is partially correct
20	Partially correct	1 ms	344 KB	Output is partially correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	1 ms	604 KB	Output is correct
23	Correct	1 ms	600 KB	Output is correct
24	Correct	1 ms	604 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Partially correct	0 ms	348 KB	Output is partially correct

Subtask #3
9.9 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	0 ms	344 KB	Output is partially correct
2	Partially correct	0 ms	348 KB	Output is partially correct
3	Partially correct	0 ms	348 KB	Output is partially correct
4	Partially correct	0 ms	348 KB	Output is partially correct
5	Partially correct	0 ms	348 KB	Output is partially correct
6	Correct	0 ms	452 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Partially correct	1 ms	348 KB	Output is partially correct
12	Partially correct	1 ms	856 KB	Output is partially correct
13	Partially correct	1 ms	604 KB	Output is partially correct
14	Partially correct	1 ms	348 KB	Output is partially correct
15	Partially correct	1 ms	604 KB	Output is partially correct
16	Partially correct	1 ms	604 KB	Output is partially correct
17	Partially correct	1 ms	604 KB	Output is partially correct
18	Partially correct	1 ms	348 KB	Output is partially correct
19	Partially correct	1 ms	348 KB	Output is partially correct
20	Partially correct	1 ms	344 KB	Output is partially correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	1 ms	604 KB	Output is correct
23	Correct	1 ms	600 KB	Output is correct
24	Correct	1 ms	604 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Partially correct	0 ms	348 KB	Output is partially correct
27	Partially correct	61 ms	16928 KB	Output is partially correct
28	Partially correct	51 ms	18012 KB	Output is partially correct
29	Partially correct	46 ms	16716 KB	Output is partially correct
30	Partially correct	57 ms	19028 KB	Output is partially correct
31	Partially correct	43 ms	14672 KB	Output is partially correct
32	Partially correct	48 ms	14420 KB	Output is partially correct
33	Partially correct	13 ms	12636 KB	Output is partially correct
34	Partially correct	9 ms	8792 KB	Output is partially correct
35	Partially correct	20 ms	15708 KB	Output is partially correct
36	Correct	49 ms	19284 KB	Output is correct
37	Correct	84 ms	19576 KB	Output is correct
38	Correct	11 ms	10332 KB	Output is correct
39	Correct	46 ms	18260 KB	Output is correct
40	Correct	1 ms	348 KB	Output is correct
41	Partially correct	0 ms	348 KB	Output is partially correct

답안 #989067

Compilation message

Subtask #1 6.9 / 23.0

Subtask #2 13.2 / 44.0

Subtask #3 9.9 / 33.0

Subtask #1
6.9 / 23.0

Subtask #2
13.2 / 44.0

Subtask #3
9.9 / 33.0