oj.uz

Submission #279960

# Submission time Handle Problem Language Result Execution time Memory
279960 2020-08-22T12:22:37 Z Haunted_Cpp RMQ (NOI17_rmq) C++17
46.1 / 100
 175 ms 5784 KB 
/**
 *  author: Haunted_Cpp
**/
 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
 
template<typename T> ostream &operator << (ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream &operator << (ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream &operator << (ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
 
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
 
#ifdef LOCAL
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#else
#define debug(...) 47
#endif

class SegmentTree {
private:
  struct Node {
    int mn, lazy;
    Node() {
      mn = 1e9;
      lazy = -1;
    }
  };
  const int LO, HI;
  vector<Node> seg;
  void push(int l, int r, int node) {
    if (seg[node].lazy == -1) return;
    seg[node].mn = seg[node].lazy;
    if (l != r) {
      seg[2 * node + 1].lazy = seg[node].lazy;
      seg[2 * node + 2].lazy = seg[node].lazy;
    }
    seg[node].lazy = -1;
  }
  void range_set(int ql, int qr, int delta, int l, int r, int node) {
    push(l, r, node);
    if (l > qr || r < ql) return;
    if (l >= ql && r <= qr) {
      seg[node].lazy = delta;
      push(l, r, node);
      return;
    }
    const int mid = l + (r - l) / 2;
    range_set(ql, qr, delta, l, mid, 2 * node + 1);
    range_set(ql, qr, delta, mid + 1, r, 2 * node + 2);
    seg[node].mn = min(seg[2 * node + 1].mn, seg[2 * node + 2].mn);
  }
  int range_query(int ql, int qr, int l, int r, int node) {
    push(l, r, node);
    if (l > qr || r < ql) return 1e9;
    if (l >= ql && r <= qr) return seg[node].mn;
    const int mid = l + (r - l) / 2;
    return min(range_query(ql, qr, l, mid, 2 * node + 1), range_query(ql, qr, mid + 1, r, 2 * node + 2));
  }
  void solve(int l, int r, int node) {
    push(l, r, node);
    if (l == r) {
      if (seg[node].mn > 1e7) cout << 0 << '\n';
      else cout << seg[node].mn << ' ';
      return;
    }
    const int mid = l + (r - l) / 2;
    solve(l, mid, 2 * node + 1);
    solve(mid + 1, r, 2 * node + 2);
  }
public:
  SegmentTree(int n) : LO(0), HI(n - 1) {
    seg.clear();
    seg.resize(4 * n);
  }
  void range_set(int ql, int qr, int delta) {
    range_set(ql, qr, delta, LO, HI, 0);
  }
  int rmq(int ql, int qr) {
    return range_query(ql, qr, LO, HI, 0);
  }
  void solve() {
    solve(LO, HI, 0);
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); 
  int n, m;
  cin >> n >> m;
  vector<tuple<int, int, int>> arr(m);
  for (int i = 0; i < m; i++) {
    int st, et, w;
    cin >> st >> et >> w;
    arr[i] = {st, et, w};
  }
  if (n <= 10) {
    vector<int> ans(n);
    iota(ans.begin(), ans.end(), 0);
    do {
      for (int i = 0; i < m; i++) {
        const int st = get<0>(arr[i]);
        const int et = get<1>(arr[i]);
        const int mn = get<2>(arr[i]);
        const int is = *min_element(ans.begin() + st, ans.begin() + et + 1);
        if (is != mn) {
          goto fim;
          break;
        }
      }
      for (auto to : ans) cout << to << ' ';
      return 0;
      fim:;
    } while(next_permutation(ans.begin(), ans.end()));
    for (int i = 0; i < n; i++) {
      cout << -1 << ' ';
    }
    return 0;
  } else {
    sort(arr.begin(), arr.end(), [&](auto x, auto y) {
      return get<2>(x) < get<2>(y);
    });
    SegmentTree seg(n);
    for (int i = 0; i < m; i++) {
      const int st = get<0>(arr[i]);
      const int et = get<1>(arr[i]);
      const int mn = get<2>(arr[i]);
      seg.range_set(st, et, mn);
    }
    for (int i = 0; i < m; i++) {
      const int st = get<0>(arr[i]);
      const int et = get<1>(arr[i]);
      const int mn = get<2>(arr[i]);
      const int is = seg.rmq(st, et);
      if (is != mn) {
        for (int j = 0; j < n; j++) {
          cout << -1 << ' ';
        }
        cout << '\n';
        return 0;
      }
    }
    seg.solve();
    cout << '\n';
  }
  return 0;
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 14 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 54 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 51 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct

Subtask #2
13.2 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 14 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 54 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 51 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Partially correct 1 ms 416 KB Output is partially correct
13 Partially correct 1 ms 384 KB Output is partially correct
14 Partially correct 1 ms 384 KB Output is partially correct
15 Partially correct 1 ms 384 KB Output is partially correct
16 Partially correct 1 ms 384 KB Output is partially correct
17 Partially correct 2 ms 384 KB Output is partially correct
18 Partially correct 1 ms 384 KB Output is partially correct
19 Partially correct 1 ms 384 KB Output is partially correct
20 Partially correct 1 ms 384 KB Output is partially correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 512 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 0 ms 384 KB Output is correct

Subtask #3
9.9 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 14 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 54 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 51 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Partially correct 1 ms 416 KB Output is partially correct
13 Partially correct 1 ms 384 KB Output is partially correct
14 Partially correct 1 ms 384 KB Output is partially correct
15 Partially correct 1 ms 384 KB Output is partially correct
16 Partially correct 1 ms 384 KB Output is partially correct
17 Partially correct 2 ms 384 KB Output is partially correct
18 Partially correct 1 ms 384 KB Output is partially correct
19 Partially correct 1 ms 384 KB Output is partially correct
20 Partially correct 1 ms 384 KB Output is partially correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 512 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 0 ms 384 KB Output is correct
27 Partially correct 169 ms 5296 KB Output is partially correct
28 Partially correct 155 ms 5240 KB Output is partially correct
29 Partially correct 120 ms 4600 KB Output is partially correct
30 Partially correct 175 ms 5624 KB Output is partially correct
31 Partially correct 125 ms 4400 KB Output is partially correct
32 Partially correct 153 ms 4612 KB Output is partially correct
33 Partially correct 14 ms 3072 KB Output is partially correct
34 Partially correct 8 ms 2304 KB Output is partially correct
35 Partially correct 42 ms 3836 KB Output is partially correct
36 Correct 80 ms 4984 KB Output is correct
37 Correct 118 ms 5784 KB Output is correct
38 Correct 8 ms 2560 KB Output is correct
39 Correct 111 ms 5112 KB Output is correct
40 Correct 1 ms 384 KB Output is correct
41 Correct 1 ms 360 KB Output is correct