oj.uz

Submission #863187

# Submission time Handle Problem Language Result Execution time Memory
863187 2023-10-19T18:06:33 Z truongdoan2012 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
100 / 100
 2263 ms 179144 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

using i64 = long long;

class segtree {
  public:
  struct node {
    // don't forget to set default value (used for leaves)
    // not necessarily neutral element!
    i64 a = 0;

    void apply(int l, int r, i64 v) {
      a = v;
    }
  };

  node unite(const node &a, const node &b) const {
    node res;
    res.a = max(a.a, b.a);
    return res;
  }

  inline void push(int x, int l, int r) {
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    // push from x into (x + 1) and z
/*
    if (tree[x].add != 0) {
      tree[x + 1].apply(l, y, tree[x].add);
      tree[z].apply(y + 1, r, tree[x].add);
      tree[x].add = 0;
    }
*/
  }

  inline void pull(int x, int z) {
    tree[x] = unite(tree[x + 1], tree[z]);
  }

  int n;
  vector<node> tree;

  void build(int x, int l, int r) {
    if (l == r) {
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y);
    build(z, y + 1, r);
    pull(x, z);
  }

  template <typename M>
  void build(int x, int l, int r, const vector<M> &v) {
    if (l == r) {
      tree[x].apply(l, r, v[l]);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y, v);
    build(z, y + 1, r, v);
    pull(x, z);
  }

  node get(int x, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
      return tree[x];
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    node res{};
    if (rr <= y) {
      res = get(x + 1, l, y, ll, rr);
    } else {
      if (ll > y) {
        res = get(z, y + 1, r, ll, rr);
      } else {
        res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
      }
    }
    pull(x, z);
    return res;
  }

  template <typename... M>
  void modify(int x, int l, int r, int ll, int rr, const M&... v) {
    if (ll <= l && r <= rr) {
      tree[x].apply(l, r, v...);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    if (ll <= y) {
      modify(x + 1, l, y, ll, rr, v...);
    }
    if (rr > y) {
      modify(z, y + 1, r, ll, rr, v...);
    }
    pull(x, z);
  }

  int find_first_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[x + 1])) {
      res = find_first_knowingly(x + 1, l, y, f);
    } else {
      res = find_first_knowingly(z, y + 1, r, f);
    }
    pull(x, z);
    return res;
  }

  int find_first(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_first_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (ll <= y) {
      res = find_first(x + 1, l, y, ll, rr, f);
    }
    if (rr > y && res == -1) {
      res = find_first(z, y + 1, r, ll, rr, f);
    }
    pull(x, z);
    return res;
  }

  int find_last_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[z])) {
      res = find_last_knowingly(z, y + 1, r, f);
    } else {
      res = find_last_knowingly(x + 1, l, y, f);
    }
    pull(x, z);
    return res;
  }

  int find_last(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_last_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (rr > y) {
      res = find_last(z, y + 1, r, ll, rr, f);
    }
    if (ll <= y && res == -1) {
      res = find_last(x + 1, l, y, ll, rr, f);
    }
    pull(x, z);
    return res;
  }

  segtree(int _n) : n(_n) {
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1);
  }

  template <typename M>
  segtree(const vector<M> &v) {
    n = v.size();
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1, v);
  }

  node get(int ll, int rr) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return get(0, 0, n - 1, ll, rr);
  }

  node get(int p) {
    assert(0 <= p && p <= n - 1);
    return get(0, 0, n - 1, p, p);
  }

  template <typename... M>
  void modify(int ll, int rr, const M&... v) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    modify(0, 0, n - 1, ll, rr, v...);
  }

  // find_first and find_last call all FALSE elements
  // to the left (right) of the sought position exactly once

  int find_first(int ll, int rr, const function<bool(const node&)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_first(0, 0, n - 1, ll, rr, f);
  }

  int find_last(int ll, int rr, const function<bool(const node&)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_last(0, 0, n - 1, ll, rr, f);
  }
};
void solve() {
  int n, m;
  cin >> n >> m;
  vector<i64> a(n), ans(m, 1);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  segtree ST(n);
  map<int, vector<array<i64, 3>>> mp;
  stack<int> st;
  for (int i = 0; i < m; i++) {
    int u, v, c;
    cin >> u >> v >> c;
    mp[--v].push_back({--u, c, i});
  }
  for (int i = 0; i < n; i++) {
    while (!st.empty() && a[st.top()] <= a[i]) {
      st.pop();
    }
    //a[pv] > a[i]
    if (!st.empty())
      ST.modify(st.top(), st.top(), a[st.top()] + a[i]);
    for (auto [l, w, id] : mp[i]) {
      ans[id] = ST.get(l, i).a <= w;
    }
    st.push(i);
  }
  for (int i = 0; i < m; i++) {
    cout << ans[i] << '\n';
  }
}

int main() {
  cin.tie(nullptr) -> sync_with_stdio(false);
  int TC = 1;
  //cin >> TC;
  while (TC--) {
    solve();
  }
}

Compilation message

sortbooks.cpp: In member function 'void segtree::push(int, int, int)':
sortbooks.cpp:33:9: warning: unused variable 'z' [-Wunused-variable]
   33 |     int z = x + ((y - l + 1) << 1);
      |         ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 3 ms 1228 KB Output is correct
13 Correct 4 ms 1116 KB Output is correct
14 Correct 5 ms 1372 KB Output is correct
15 Correct 5 ms 1232 KB Output is correct
16 Correct 4 ms 1116 KB Output is correct
17 Correct 4 ms 1624 KB Output is correct
18 Correct 4 ms 1240 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2000 ms 144536 KB Output is correct
2 Correct 1967 ms 177384 KB Output is correct
3 Correct 2167 ms 177004 KB Output is correct
4 Correct 2263 ms 177356 KB Output is correct
5 Correct 1864 ms 177516 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 16064 KB Output is correct
2 Correct 98 ms 16864 KB Output is correct
3 Correct 91 ms 16720 KB Output is correct
4 Correct 90 ms 16724 KB Output is correct
5 Correct 104 ms 16652 KB Output is correct
6 Correct 69 ms 16336 KB Output is correct
7 Correct 83 ms 16336 KB Output is correct
8 Correct 83 ms 16092 KB Output is correct
9 Correct 31 ms 5640 KB Output is correct
10 Correct 78 ms 16064 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 3 ms 1228 KB Output is correct
13 Correct 4 ms 1116 KB Output is correct
14 Correct 5 ms 1372 KB Output is correct
15 Correct 5 ms 1232 KB Output is correct
16 Correct 4 ms 1116 KB Output is correct
17 Correct 4 ms 1624 KB Output is correct
18 Correct 4 ms 1240 KB Output is correct
19 Correct 272 ms 35828 KB Output is correct
20 Correct 262 ms 35832 KB Output is correct
21 Correct 206 ms 36172 KB Output is correct
22 Correct 228 ms 36176 KB Output is correct
23 Correct 233 ms 36068 KB Output is correct
24 Correct 164 ms 35920 KB Output is correct
25 Correct 173 ms 35976 KB Output is correct
26 Correct 200 ms 35924 KB Output is correct
27 Correct 200 ms 35928 KB Output is correct
28 Correct 213 ms 35864 KB Output is correct
29 Correct 220 ms 35812 KB Output is correct
30 Correct 229 ms 35924 KB Output is correct
31 Correct 221 ms 35864 KB Output is correct
32 Correct 225 ms 35800 KB Output is correct
33 Correct 233 ms 35812 KB Output is correct
34 Correct 154 ms 34912 KB Output is correct
35 Correct 180 ms 34896 KB Output is correct
36 Correct 160 ms 34792 KB Output is correct
37 Correct 148 ms 34776 KB Output is correct
38 Correct 150 ms 34912 KB Output is correct
39 Correct 211 ms 33912 KB Output is correct
40 Correct 155 ms 25676 KB Output is correct
41 Correct 184 ms 33324 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 3 ms 1228 KB Output is correct
13 Correct 4 ms 1116 KB Output is correct
14 Correct 5 ms 1372 KB Output is correct
15 Correct 5 ms 1232 KB Output is correct
16 Correct 4 ms 1116 KB Output is correct
17 Correct 4 ms 1624 KB Output is correct
18 Correct 4 ms 1240 KB Output is correct
19 Correct 2000 ms 144536 KB Output is correct
20 Correct 1967 ms 177384 KB Output is correct
21 Correct 2167 ms 177004 KB Output is correct
22 Correct 2263 ms 177356 KB Output is correct
23 Correct 1864 ms 177516 KB Output is correct
24 Correct 124 ms 16064 KB Output is correct
25 Correct 98 ms 16864 KB Output is correct
26 Correct 91 ms 16720 KB Output is correct
27 Correct 90 ms 16724 KB Output is correct
28 Correct 104 ms 16652 KB Output is correct
29 Correct 69 ms 16336 KB Output is correct
30 Correct 83 ms 16336 KB Output is correct
31 Correct 83 ms 16092 KB Output is correct
32 Correct 31 ms 5640 KB Output is correct
33 Correct 78 ms 16064 KB Output is correct
34 Correct 272 ms 35828 KB Output is correct
35 Correct 262 ms 35832 KB Output is correct
36 Correct 206 ms 36172 KB Output is correct
37 Correct 228 ms 36176 KB Output is correct
38 Correct 233 ms 36068 KB Output is correct
39 Correct 164 ms 35920 KB Output is correct
40 Correct 173 ms 35976 KB Output is correct
41 Correct 200 ms 35924 KB Output is correct
42 Correct 200 ms 35928 KB Output is correct
43 Correct 213 ms 35864 KB Output is correct
44 Correct 220 ms 35812 KB Output is correct
45 Correct 229 ms 35924 KB Output is correct
46 Correct 221 ms 35864 KB Output is correct
47 Correct 225 ms 35800 KB Output is correct
48 Correct 233 ms 35812 KB Output is correct
49 Correct 154 ms 34912 KB Output is correct
50 Correct 180 ms 34896 KB Output is correct
51 Correct 160 ms 34792 KB Output is correct
52 Correct 148 ms 34776 KB Output is correct
53 Correct 150 ms 34912 KB Output is correct
54 Correct 211 ms 33912 KB Output is correct
55 Correct 155 ms 25676 KB Output is correct
56 Correct 184 ms 33324 KB Output is correct
57 Correct 1952 ms 178608 KB Output is correct
58 Correct 1834 ms 178112 KB Output is correct
59 Correct 1735 ms 179096 KB Output is correct
60 Correct 1753 ms 179144 KB Output is correct
61 Correct 1791 ms 179012 KB Output is correct
62 Correct 1786 ms 179136 KB Output is correct
63 Correct 963 ms 176872 KB Output is correct
64 Correct 983 ms 176720 KB Output is correct
65 Correct 1600 ms 179056 KB Output is correct
66 Correct 1663 ms 179120 KB Output is correct
67 Correct 1693 ms 178920 KB Output is correct
68 Correct 1766 ms 178180 KB Output is correct
69 Correct 1841 ms 178400 KB Output is correct
70 Correct 1911 ms 178448 KB Output is correct
71 Correct 1659 ms 178188 KB Output is correct
72 Correct 1725 ms 178496 KB Output is correct
73 Correct 933 ms 168284 KB Output is correct
74 Correct 886 ms 169448 KB Output is correct
75 Correct 850 ms 168632 KB Output is correct
76 Correct 906 ms 168532 KB Output is correct
77 Correct 889 ms 168164 KB Output is correct
78 Correct 1475 ms 169348 KB Output is correct
79 Correct 983 ms 113956 KB Output is correct
80 Correct 1607 ms 165916 KB Output is correct