oj.uz

Submission #894239

# Submission time Handle Problem Language Result Execution time Memory
894239 2023-12-28T03:05:01 Z Olympia Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
77 / 100
 3000 ms 251608 KB 
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <cassert>
#include <algorithm>
using namespace std;
struct Node {
    int mx;
    int mn;
    int val;
    vector<int> v;
    Node () {
        this->mx = INT_MIN, this->mn = INT_MAX, this->val = 0;
    }
};
struct SegmentTree {
    vector<Node> vec;
    vector<int> nodes;
    Node merge (Node &left, Node &right) {
        Node ans = {};
        ans.mn = min(left.mn, right.mn);
        ans.mx = max(left.mx, right.mx);
        ans.val = max(left.val, right.val);
        if (right.mx < left.mx) {
            ans.val = max(ans.val, left.mx + right.mx);
        } else if (right.mn < left.mx) {
            int l = 0;
            int r = right.v.size() - 1;
            while (l != r) {
                int m = (l + r + 1)/2;
                if (right.v[m] < left.mx) {
                    l = m;
                } else {
                    r = m - 1;
                }
            }
            ans.val = max(ans.val, right.v[l] + left.mx);
        }
        return ans;
    }
    vector<int> intervals;
    void query (int dum, int tl, int tr, int l, int r) {
        if (tl >= l && tr <= r) {
            intervals.push_back(dum);
        } else if (tl <= r && tr >= l) {
            query(2 * dum + 1, tl, (tl + tr)/2,l, r), query(2 * dum + 2, (tl + tr)/2 + 1, tr, l, r);
        }
    }
    int query (int l, int r) {
        intervals.clear();
        query(0, 0, (int)vec.size()/2 - 1, l, r);
        Node ans = vec[intervals[0]];
        for (int i = 1; i < intervals.size(); i++) {
            ans = merge(ans, vec[intervals[i]]);
        }
        return ans.val;
    }
    void build (int dum, int tl, int tr) {
        if (tl == tr) {
            vec[dum] = Node();
            vec[dum].mn = vec[dum].mx = nodes[tl], vec[dum].v = {nodes[tl]};
        } else {
        build(2 * dum + 1, tl, (tl + tr)/2), build(2 * dum + 2, (tl + tr)/2 + 1, tr);
        vec[dum] = merge(vec[2 * dum + 1], vec[2 * dum + 2]);
        vec[dum].v.reserve(vec[2 * dum + 1].v.size() + vec[2 * dum + 2].v.size());
        std::merge(vec[2 * dum + 1].v.begin(), vec[2 * dum + 1].v.end(),
                   vec[2 * dum + 2].v.begin(), vec[2 * dum + 2].v.end(),
                   std::back_inserter(vec[dum].v));
        }
    }
    SegmentTree (vector<int> nodes) {
        this->nodes = nodes;
        int n = nodes.size();
        n = (1 << (int)log2(n)) * 2;
        vec.assign(2 * n, Node());
        this->nodes.reserve(vec.size());
        while (this->nodes.size() < vec.size()) {
            this->nodes.push_back((int)1e9);
        }
        build(0, 0, (int)vec.size()/2 - 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:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int i = 1; i < intervals.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 600 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 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 3 ms 860 KB Output is correct
12 Correct 4 ms 2140 KB Output is correct
13 Correct 4 ms 2140 KB Output is correct
14 Correct 6 ms 2140 KB Output is correct
15 Correct 6 ms 2176 KB Output is correct
16 Correct 5 ms 2004 KB Output is correct
17 Correct 5 ms 2140 KB Output is correct
18 Correct 5 ms 2132 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1987 ms 251512 KB Output is correct
2 Correct 1997 ms 250044 KB Output is correct
3 Correct 2058 ms 250048 KB Output is correct
4 Correct 2086 ms 251608 KB Output is correct
5 Correct 1375 ms 251400 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 29204 KB Output is correct
2 Correct 146 ms 29220 KB Output is correct
3 Correct 103 ms 29260 KB Output is correct
4 Correct 100 ms 29244 KB Output is correct
5 Correct 103 ms 29356 KB Output is correct
6 Correct 86 ms 29248 KB Output is correct
7 Correct 84 ms 29176 KB Output is correct
8 Correct 297 ms 29060 KB Output is correct
9 Correct 37 ms 1624 KB Output is correct
10 Correct 292 ms 29068 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 3 ms 860 KB Output is correct
12 Correct 4 ms 2140 KB Output is correct
13 Correct 4 ms 2140 KB Output is correct
14 Correct 6 ms 2140 KB Output is correct
15 Correct 6 ms 2176 KB Output is correct
16 Correct 5 ms 2004 KB Output is correct
17 Correct 5 ms 2140 KB Output is correct
18 Correct 5 ms 2132 KB Output is correct
19 Correct 326 ms 60240 KB Output is correct
20 Correct 338 ms 60212 KB Output is correct
21 Correct 269 ms 60224 KB Output is correct
22 Correct 266 ms 60376 KB Output is correct
23 Correct 275 ms 60184 KB Output is correct
24 Correct 196 ms 60352 KB Output is correct
25 Correct 195 ms 60348 KB Output is correct
26 Correct 229 ms 60588 KB Output is correct
27 Correct 222 ms 60212 KB Output is correct
28 Correct 234 ms 59904 KB Output is correct
29 Correct 239 ms 60212 KB Output is correct
30 Correct 248 ms 59884 KB Output is correct
31 Correct 245 ms 59828 KB Output is correct
32 Correct 245 ms 60196 KB Output is correct
33 Correct 238 ms 59888 KB Output is correct
34 Correct 189 ms 60344 KB Output is correct
35 Correct 189 ms 60640 KB Output is correct
36 Correct 189 ms 59972 KB Output is correct
37 Correct 192 ms 60004 KB Output is correct
38 Correct 192 ms 60364 KB Output is correct
39 Correct 969 ms 59588 KB Output is correct
40 Correct 1543 ms 58968 KB Output is correct
41 Correct 1178 ms 59560 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 3 ms 860 KB Output is correct
12 Correct 4 ms 2140 KB Output is correct
13 Correct 4 ms 2140 KB Output is correct
14 Correct 6 ms 2140 KB Output is correct
15 Correct 6 ms 2176 KB Output is correct
16 Correct 5 ms 2004 KB Output is correct
17 Correct 5 ms 2140 KB Output is correct
18 Correct 5 ms 2132 KB Output is correct
19 Correct 1987 ms 251512 KB Output is correct
20 Correct 1997 ms 250044 KB Output is correct
21 Correct 2058 ms 250048 KB Output is correct
22 Correct 2086 ms 251608 KB Output is correct
23 Correct 1375 ms 251400 KB Output is correct
24 Correct 152 ms 29204 KB Output is correct
25 Correct 146 ms 29220 KB Output is correct
26 Correct 103 ms 29260 KB Output is correct
27 Correct 100 ms 29244 KB Output is correct
28 Correct 103 ms 29356 KB Output is correct
29 Correct 86 ms 29248 KB Output is correct
30 Correct 84 ms 29176 KB Output is correct
31 Correct 297 ms 29060 KB Output is correct
32 Correct 37 ms 1624 KB Output is correct
33 Correct 292 ms 29068 KB Output is correct
34 Correct 326 ms 60240 KB Output is correct
35 Correct 338 ms 60212 KB Output is correct
36 Correct 269 ms 60224 KB Output is correct
37 Correct 266 ms 60376 KB Output is correct
38 Correct 275 ms 60184 KB Output is correct
39 Correct 196 ms 60352 KB Output is correct
40 Correct 195 ms 60348 KB Output is correct
41 Correct 229 ms 60588 KB Output is correct
42 Correct 222 ms 60212 KB Output is correct
43 Correct 234 ms 59904 KB Output is correct
44 Correct 239 ms 60212 KB Output is correct
45 Correct 248 ms 59884 KB Output is correct
46 Correct 245 ms 59828 KB Output is correct
47 Correct 245 ms 60196 KB Output is correct
48 Correct 238 ms 59888 KB Output is correct
49 Correct 189 ms 60344 KB Output is correct
50 Correct 189 ms 60640 KB Output is correct
51 Correct 189 ms 59972 KB Output is correct
52 Correct 192 ms 60004 KB Output is correct
53 Correct 192 ms 60364 KB Output is correct
54 Correct 969 ms 59588 KB Output is correct
55 Correct 1543 ms 58968 KB Output is correct
56 Correct 1178 ms 59560 KB Output is correct
57 Correct 2175 ms 242588 KB Output is correct
58 Correct 2119 ms 234128 KB Output is correct
59 Correct 2134 ms 234068 KB Output is correct
60 Correct 2019 ms 234084 KB Output is correct
61 Correct 2053 ms 234136 KB Output is correct
62 Correct 2082 ms 234128 KB Output is correct
63 Correct 992 ms 234216 KB Output is correct
64 Correct 1022 ms 234056 KB Output is correct
65 Correct 1360 ms 234116 KB Output is correct
66 Correct 1346 ms 233996 KB Output is correct
67 Correct 1371 ms 233924 KB Output is correct
68 Correct 1435 ms 234148 KB Output is correct
69 Correct 1390 ms 233876 KB Output is correct
70 Correct 1433 ms 234168 KB Output is correct
71 Correct 1412 ms 234016 KB Output is correct
72 Correct 1449 ms 233944 KB Output is correct
73 Correct 1082 ms 234036 KB Output is correct
74 Correct 1051 ms 234144 KB Output is correct
75 Correct 1047 ms 234116 KB Output is correct
76 Correct 1002 ms 234064 KB Output is correct
77 Correct 1071 ms 234012 KB Output is correct
78 Execution timed out 3050 ms 233924 KB Time limit exceeded
79 Halted 0 ms 0 KB -