oj.uz

Submission #989067

# Submission time Handle Problem Language Result Execution time Memory
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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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