oj.uz

Submission #894304

# Submission time Handle Problem Language Result Execution time Memory
894304 2023-12-28T04:20:30 Z Olympia Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
100 / 100
 2085 ms 244508 KB 
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <cassert>
#include <algorithm>

using namespace std;

const int MAX = ((1 << 20) + 7);

struct Node {
    int mx;
    int val;
    Node () {
        this->mx = -INT_MAX, this->val = 0;
    }
    Node(int mx) {
        this->mx = mx, this->val = 0;
    }
} vec[2 * MAX];

struct SegmentTree {
    vector<int> nodes;
    vector<int> v[2 * MAX];
    int sz;

    Node merge(Node &left, int ind) {
        Node ans = {max(left.mx, vec[ind].mx)};
        ans.val = max(left.val, vec[ind].val);
        if (vec[ind].mx < left.mx) {
            ans.val = max(ans.val, left.mx + vec[ind].mx);
        } else if (v[ind][0] < left.mx) {
            ans.val = max(ans.val, *(--lower_bound(v[ind].begin(), v[ind].end(), left.mx)) + left.mx);
        }
        return ans;
    }

    int query(int l, int r) {
        r += 1;
        vector<int> vec1, vec2;
        for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
            if (l & 1) {
                vec1.push_back(l++);
            }
            if (r & 1) {
                vec2.push_back(--r);
            }
        }
        reverse(vec2.begin(), vec2.end());
        for (int x: vec2) {
            vec1.push_back(x);
        }
        Node ans = vec[vec1[0]];
        for (int i = 1; i < vec1.size(); i++) {
            ans = merge(ans, vec1[i]);
        }
        return ans.val;
    }

    void build(int dum, int tl, int tr) {
        if (tl == tr) {
            vec[dum] = Node(nodes[tl]);
            v[dum] = {nodes[tl]};
        } else {
            build(2 * dum, tl, (tl + tr) / 2), build(2 * dum + 1, (tl + tr) / 2 + 1, tr);
            vec[dum] = merge(vec[2 * dum], 2 * dum + 1);
            std::merge(v[2 * dum].begin(), v[2 * dum].end(),
                       v[2 * dum + 1].begin(), v[2 * dum + 1].end(),
                       std::back_inserter(v[dum]));
        }
    }

    SegmentTree(vector<int> nodes) {
        this->nodes = nodes;
        int n = nodes.size();
        n = (1 << (int) log2(n)) * 2;
        this->sz = n;
        this->nodes.reserve(2 * sz);
        while (this->nodes.size() < 2 * sz) {
            this->nodes.push_back((int) 1e9);
        }
        build(1, 0, sz - 1);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    cin >> n >> q;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    SegmentTree st(v);
    while (q--) {
        int l, r, k;
        cin >> l >> r >> k;
        l--, r--;
        cout << (st.query(l, r) <= k) << '\n';
    }
}

Compilation message

sortbooks.cpp: In member function 'int SegmentTree::query(int, int)':
sortbooks.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for (int i = 1; i < vec1.size(); i++) {
      |                         ~~^~~~~~~~~~~~~
sortbooks.cpp: In constructor 'SegmentTree::SegmentTree(std::vector<int>)':
sortbooks.cpp:82:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   82 |         while (this->nodes.size() < 2 * sz) {
      |                ~~~~~~~~~~~~~~~~~~~^~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 66132 KB Output is correct
2 Correct 34 ms 65924 KB Output is correct
3 Correct 34 ms 66040 KB Output is correct
4 Correct 34 ms 65876 KB Output is correct
5 Correct 34 ms 66036 KB Output is correct
6 Correct 35 ms 66140 KB Output is correct
7 Correct 34 ms 65988 KB Output is correct
8 Correct 34 ms 65992 KB Output is correct
9 Correct 34 ms 66132 KB Output is correct
10 Correct 39 ms 66140 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 66132 KB Output is correct
2 Correct 34 ms 65924 KB Output is correct
3 Correct 34 ms 66040 KB Output is correct
4 Correct 34 ms 65876 KB Output is correct
5 Correct 34 ms 66036 KB Output is correct
6 Correct 35 ms 66140 KB Output is correct
7 Correct 34 ms 65988 KB Output is correct
8 Correct 34 ms 65992 KB Output is correct
9 Correct 34 ms 66132 KB Output is correct
10 Correct 39 ms 66140 KB Output is correct
11 Correct 36 ms 66132 KB Output is correct
12 Correct 37 ms 66908 KB Output is correct
13 Correct 38 ms 66908 KB Output is correct
14 Correct 40 ms 66908 KB Output is correct
15 Correct 42 ms 66924 KB Output is correct
16 Correct 39 ms 66896 KB Output is correct
17 Correct 37 ms 66908 KB Output is correct
18 Correct 38 ms 66904 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2080 ms 221448 KB Output is correct
2 Correct 2074 ms 221452 KB Output is correct
3 Correct 2078 ms 221764 KB Output is correct
4 Correct 2060 ms 221456 KB Output is correct
5 Correct 1739 ms 221624 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 83656 KB Output is correct
2 Correct 173 ms 83660 KB Output is correct
3 Correct 155 ms 83780 KB Output is correct
4 Correct 145 ms 83776 KB Output is correct
5 Correct 145 ms 83656 KB Output is correct
6 Correct 128 ms 83656 KB Output is correct
7 Correct 127 ms 83668 KB Output is correct
8 Correct 133 ms 83652 KB Output is correct
9 Correct 70 ms 66732 KB Output is correct
10 Correct 132 ms 83660 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 66132 KB Output is correct
2 Correct 34 ms 65924 KB Output is correct
3 Correct 34 ms 66040 KB Output is correct
4 Correct 34 ms 65876 KB Output is correct
5 Correct 34 ms 66036 KB Output is correct
6 Correct 35 ms 66140 KB Output is correct
7 Correct 34 ms 65988 KB Output is correct
8 Correct 34 ms 65992 KB Output is correct
9 Correct 34 ms 66132 KB Output is correct
10 Correct 39 ms 66140 KB Output is correct
11 Correct 36 ms 66132 KB Output is correct
12 Correct 37 ms 66908 KB Output is correct
13 Correct 38 ms 66908 KB Output is correct
14 Correct 40 ms 66908 KB Output is correct
15 Correct 42 ms 66924 KB Output is correct
16 Correct 39 ms 66896 KB Output is correct
17 Correct 37 ms 66908 KB Output is correct
18 Correct 38 ms 66904 KB Output is correct
19 Correct 363 ms 102504 KB Output is correct
20 Correct 363 ms 102724 KB Output is correct
21 Correct 322 ms 102468 KB Output is correct
22 Correct 322 ms 102476 KB Output is correct
23 Correct 333 ms 102472 KB Output is correct
24 Correct 273 ms 102464 KB Output is correct
25 Correct 260 ms 102464 KB Output is correct
26 Correct 302 ms 102464 KB Output is correct
27 Correct 312 ms 102724 KB Output is correct
28 Correct 305 ms 102476 KB Output is correct
29 Correct 317 ms 102464 KB Output is correct
30 Correct 313 ms 102320 KB Output is correct
31 Correct 337 ms 102456 KB Output is correct
32 Correct 313 ms 102464 KB Output is correct
33 Correct 337 ms 102720 KB Output is correct
34 Correct 251 ms 102468 KB Output is correct
35 Correct 255 ms 102464 KB Output is correct
36 Correct 247 ms 102344 KB Output is correct
37 Correct 247 ms 102464 KB Output is correct
38 Correct 247 ms 102464 KB Output is correct
39 Correct 297 ms 102464 KB Output is correct
40 Correct 240 ms 102208 KB Output is correct
41 Correct 257 ms 102392 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 66132 KB Output is correct
2 Correct 34 ms 65924 KB Output is correct
3 Correct 34 ms 66040 KB Output is correct
4 Correct 34 ms 65876 KB Output is correct
5 Correct 34 ms 66036 KB Output is correct
6 Correct 35 ms 66140 KB Output is correct
7 Correct 34 ms 65988 KB Output is correct
8 Correct 34 ms 65992 KB Output is correct
9 Correct 34 ms 66132 KB Output is correct
10 Correct 39 ms 66140 KB Output is correct
11 Correct 36 ms 66132 KB Output is correct
12 Correct 37 ms 66908 KB Output is correct
13 Correct 38 ms 66908 KB Output is correct
14 Correct 40 ms 66908 KB Output is correct
15 Correct 42 ms 66924 KB Output is correct
16 Correct 39 ms 66896 KB Output is correct
17 Correct 37 ms 66908 KB Output is correct
18 Correct 38 ms 66904 KB Output is correct
19 Correct 2080 ms 221448 KB Output is correct
20 Correct 2074 ms 221452 KB Output is correct
21 Correct 2078 ms 221764 KB Output is correct
22 Correct 2060 ms 221456 KB Output is correct
23 Correct 1739 ms 221624 KB Output is correct
24 Correct 178 ms 83656 KB Output is correct
25 Correct 173 ms 83660 KB Output is correct
26 Correct 155 ms 83780 KB Output is correct
27 Correct 145 ms 83776 KB Output is correct
28 Correct 145 ms 83656 KB Output is correct
29 Correct 128 ms 83656 KB Output is correct
30 Correct 127 ms 83668 KB Output is correct
31 Correct 133 ms 83652 KB Output is correct
32 Correct 70 ms 66732 KB Output is correct
33 Correct 132 ms 83660 KB Output is correct
34 Correct 363 ms 102504 KB Output is correct
35 Correct 363 ms 102724 KB Output is correct
36 Correct 322 ms 102468 KB Output is correct
37 Correct 322 ms 102476 KB Output is correct
38 Correct 333 ms 102472 KB Output is correct
39 Correct 273 ms 102464 KB Output is correct
40 Correct 260 ms 102464 KB Output is correct
41 Correct 302 ms 102464 KB Output is correct
42 Correct 312 ms 102724 KB Output is correct
43 Correct 305 ms 102476 KB Output is correct
44 Correct 317 ms 102464 KB Output is correct
45 Correct 313 ms 102320 KB Output is correct
46 Correct 337 ms 102456 KB Output is correct
47 Correct 313 ms 102464 KB Output is correct
48 Correct 337 ms 102720 KB Output is correct
49 Correct 251 ms 102468 KB Output is correct
50 Correct 255 ms 102464 KB Output is correct
51 Correct 247 ms 102344 KB Output is correct
52 Correct 247 ms 102464 KB Output is correct
53 Correct 247 ms 102464 KB Output is correct
54 Correct 297 ms 102464 KB Output is correct
55 Correct 240 ms 102208 KB Output is correct
56 Correct 257 ms 102392 KB Output is correct
57 Correct 2085 ms 221508 KB Output is correct
58 Correct 2062 ms 221452 KB Output is correct
59 Correct 2020 ms 221508 KB Output is correct
60 Correct 1981 ms 221708 KB Output is correct
61 Correct 2051 ms 221600 KB Output is correct
62 Correct 2035 ms 221500 KB Output is correct
63 Correct 1181 ms 221584 KB Output is correct
64 Correct 1171 ms 221788 KB Output is correct
65 Correct 1719 ms 221568 KB Output is correct
66 Correct 1747 ms 221452 KB Output is correct
67 Correct 1738 ms 221452 KB Output is correct
68 Correct 1696 ms 221704 KB Output is correct
69 Correct 1700 ms 221456 KB Output is correct
70 Correct 1725 ms 221452 KB Output is correct
71 Correct 1705 ms 221484 KB Output is correct
72 Correct 1721 ms 221464 KB Output is correct
73 Correct 1106 ms 221712 KB Output is correct
74 Correct 1104 ms 221652 KB Output is correct
75 Correct 1128 ms 221456 KB Output is correct
76 Correct 1102 ms 221468 KB Output is correct
77 Correct 1101 ms 221452 KB Output is correct
78 Correct 1563 ms 236716 KB Output is correct
79 Correct 1098 ms 240568 KB Output is correct
80 Correct 1330 ms 244508 KB Output is correct