Submission #894300

#	Time	Username	Problem	Language	Result	Execution time	Memory
894300		Olympia	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	77 / 100	3050 ms	221840 KiB

sortbooks

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <cassert>
#include <algorithm>

using namespace std;

struct Node {
    int mx;
    int val;
    vector<int> v;
    Node () {
        this->mx = -INT_MAX, this->val = 0;
    }
    Node(int mx) {
        this->mx = mx, this->val = 0;
    }
} vec[2 * ((1 << 20) + 7)];

struct SegmentTree {
    vector<int> nodes;
    int sz;

    Node merge(Node &left, Node &right) {
        Node ans = {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.v[0] < left.mx) {
            ans.val = max(ans.val, *(--lower_bound(right.v.begin(), right.v.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, vec[vec1[i]]);
        }
        return ans.val;
    }

    void build(int dum, int tl, int tr) {
        if (tl == tr) {
            vec[dum] = Node(nodes[tl]);
            vec[dum].v = {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], vec[2 * dum + 1]);
            std::merge(vec[2 * dum].v.begin(), vec[2 * dum].v.end(),
                       vec[2 * dum + 1].v.begin(), vec[2 * dum + 1].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;
        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 (stderr)

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

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 0 / 23