oj.uz

Submission #894306

# Submission time Handle Problem Language Result Execution time Memory
894306 2023-12-28T04:22:29 Z Olympia Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
100 / 100
 2201 ms 221900 KB 
#include <bits/stdc++.h>


using namespace std;

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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 65884 KB Output is correct
2 Correct 33 ms 65884 KB Output is correct
3 Correct 34 ms 65872 KB Output is correct
4 Correct 34 ms 66088 KB Output is correct
5 Correct 34 ms 65900 KB Output is correct
6 Correct 34 ms 66140 KB Output is correct
7 Correct 35 ms 66128 KB Output is correct
8 Correct 34 ms 66128 KB Output is correct
9 Correct 35 ms 66128 KB Output is correct
10 Correct 34 ms 66140 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 65884 KB Output is correct
2 Correct 33 ms 65884 KB Output is correct
3 Correct 34 ms 65872 KB Output is correct
4 Correct 34 ms 66088 KB Output is correct
5 Correct 34 ms 65900 KB Output is correct
6 Correct 34 ms 66140 KB Output is correct
7 Correct 35 ms 66128 KB Output is correct
8 Correct 34 ms 66128 KB Output is correct
9 Correct 35 ms 66128 KB Output is correct
10 Correct 34 ms 66140 KB Output is correct
11 Correct 35 ms 66128 KB Output is correct
12 Correct 39 ms 66992 KB Output is correct
13 Correct 39 ms 66896 KB Output is correct
14 Correct 40 ms 66896 KB Output is correct
15 Correct 39 ms 66908 KB Output is correct
16 Correct 39 ms 66896 KB Output is correct
17 Correct 37 ms 66896 KB Output is correct
18 Correct 44 ms 66900 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2047 ms 221684 KB Output is correct
2 Correct 2031 ms 221504 KB Output is correct
3 Correct 2080 ms 221456 KB Output is correct
4 Correct 2184 ms 221524 KB Output is correct
5 Correct 1802 ms 221448 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 83660 KB Output is correct
2 Correct 176 ms 83660 KB Output is correct
3 Correct 163 ms 83788 KB Output is correct
4 Correct 167 ms 83820 KB Output is correct
5 Correct 163 ms 83660 KB Output is correct
6 Correct 131 ms 83752 KB Output is correct
7 Correct 142 ms 83772 KB Output is correct
8 Correct 143 ms 83656 KB Output is correct
9 Correct 70 ms 66384 KB Output is correct
10 Correct 150 ms 83676 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 65884 KB Output is correct
2 Correct 33 ms 65884 KB Output is correct
3 Correct 34 ms 65872 KB Output is correct
4 Correct 34 ms 66088 KB Output is correct
5 Correct 34 ms 65900 KB Output is correct
6 Correct 34 ms 66140 KB Output is correct
7 Correct 35 ms 66128 KB Output is correct
8 Correct 34 ms 66128 KB Output is correct
9 Correct 35 ms 66128 KB Output is correct
10 Correct 34 ms 66140 KB Output is correct
11 Correct 35 ms 66128 KB Output is correct
12 Correct 39 ms 66992 KB Output is correct
13 Correct 39 ms 66896 KB Output is correct
14 Correct 40 ms 66896 KB Output is correct
15 Correct 39 ms 66908 KB Output is correct
16 Correct 39 ms 66896 KB Output is correct
17 Correct 37 ms 66896 KB Output is correct
18 Correct 44 ms 66900 KB Output is correct
19 Correct 407 ms 102456 KB Output is correct
20 Correct 396 ms 102464 KB Output is correct
21 Correct 337 ms 102464 KB Output is correct
22 Correct 356 ms 102460 KB Output is correct
23 Correct 343 ms 102472 KB Output is correct
24 Correct 279 ms 102468 KB Output is correct
25 Correct 271 ms 102468 KB Output is correct
26 Correct 335 ms 102464 KB Output is correct
27 Correct 349 ms 102532 KB Output is correct
28 Correct 338 ms 102364 KB Output is correct
29 Correct 319 ms 102496 KB Output is correct
30 Correct 308 ms 102572 KB Output is correct
31 Correct 348 ms 102368 KB Output is correct
32 Correct 355 ms 102500 KB Output is correct
33 Correct 352 ms 102412 KB Output is correct
34 Correct 265 ms 102464 KB Output is correct
35 Correct 259 ms 102528 KB Output is correct
36 Correct 252 ms 102436 KB Output is correct
37 Correct 272 ms 102468 KB Output is correct
38 Correct 255 ms 102464 KB Output is correct
39 Correct 341 ms 102364 KB Output is correct
40 Correct 243 ms 101948 KB Output is correct
41 Correct 306 ms 102580 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 65884 KB Output is correct
2 Correct 33 ms 65884 KB Output is correct
3 Correct 34 ms 65872 KB Output is correct
4 Correct 34 ms 66088 KB Output is correct
5 Correct 34 ms 65900 KB Output is correct
6 Correct 34 ms 66140 KB Output is correct
7 Correct 35 ms 66128 KB Output is correct
8 Correct 34 ms 66128 KB Output is correct
9 Correct 35 ms 66128 KB Output is correct
10 Correct 34 ms 66140 KB Output is correct
11 Correct 35 ms 66128 KB Output is correct
12 Correct 39 ms 66992 KB Output is correct
13 Correct 39 ms 66896 KB Output is correct
14 Correct 40 ms 66896 KB Output is correct
15 Correct 39 ms 66908 KB Output is correct
16 Correct 39 ms 66896 KB Output is correct
17 Correct 37 ms 66896 KB Output is correct
18 Correct 44 ms 66900 KB Output is correct
19 Correct 2047 ms 221684 KB Output is correct
20 Correct 2031 ms 221504 KB Output is correct
21 Correct 2080 ms 221456 KB Output is correct
22 Correct 2184 ms 221524 KB Output is correct
23 Correct 1802 ms 221448 KB Output is correct
24 Correct 190 ms 83660 KB Output is correct
25 Correct 176 ms 83660 KB Output is correct
26 Correct 163 ms 83788 KB Output is correct
27 Correct 167 ms 83820 KB Output is correct
28 Correct 163 ms 83660 KB Output is correct
29 Correct 131 ms 83752 KB Output is correct
30 Correct 142 ms 83772 KB Output is correct
31 Correct 143 ms 83656 KB Output is correct
32 Correct 70 ms 66384 KB Output is correct
33 Correct 150 ms 83676 KB Output is correct
34 Correct 407 ms 102456 KB Output is correct
35 Correct 396 ms 102464 KB Output is correct
36 Correct 337 ms 102464 KB Output is correct
37 Correct 356 ms 102460 KB Output is correct
38 Correct 343 ms 102472 KB Output is correct
39 Correct 279 ms 102468 KB Output is correct
40 Correct 271 ms 102468 KB Output is correct
41 Correct 335 ms 102464 KB Output is correct
42 Correct 349 ms 102532 KB Output is correct
43 Correct 338 ms 102364 KB Output is correct
44 Correct 319 ms 102496 KB Output is correct
45 Correct 308 ms 102572 KB Output is correct
46 Correct 348 ms 102368 KB Output is correct
47 Correct 355 ms 102500 KB Output is correct
48 Correct 352 ms 102412 KB Output is correct
49 Correct 265 ms 102464 KB Output is correct
50 Correct 259 ms 102528 KB Output is correct
51 Correct 252 ms 102436 KB Output is correct
52 Correct 272 ms 102468 KB Output is correct
53 Correct 255 ms 102464 KB Output is correct
54 Correct 341 ms 102364 KB Output is correct
55 Correct 243 ms 101948 KB Output is correct
56 Correct 306 ms 102580 KB Output is correct
57 Correct 2201 ms 221760 KB Output is correct
58 Correct 2184 ms 221472 KB Output is correct
59 Correct 2147 ms 221456 KB Output is correct
60 Correct 2128 ms 221600 KB Output is correct
61 Correct 2144 ms 221712 KB Output is correct
62 Correct 2176 ms 221488 KB Output is correct
63 Correct 1214 ms 221624 KB Output is correct
64 Correct 1236 ms 221708 KB Output is correct
65 Correct 1847 ms 221472 KB Output is correct
66 Correct 1849 ms 221520 KB Output is correct
67 Correct 1859 ms 221448 KB Output is correct
68 Correct 1789 ms 221900 KB Output is correct
69 Correct 1752 ms 221684 KB Output is correct
70 Correct 1798 ms 221452 KB Output is correct
71 Correct 1872 ms 221452 KB Output is correct
72 Correct 1837 ms 221540 KB Output is correct
73 Correct 1152 ms 221456 KB Output is correct
74 Correct 1161 ms 221476 KB Output is correct
75 Correct 1135 ms 221632 KB Output is correct
76 Correct 1153 ms 221504 KB Output is correct
77 Correct 1119 ms 221456 KB Output is correct
78 Correct 1613 ms 221652 KB Output is correct
79 Correct 1118 ms 217912 KB Output is correct
80 Correct 1393 ms 221504 KB Output is correct