Submission #894304

#	Time	Username	Problem	Language	Result	Execution time	Memory
894304		Olympia	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	2085 ms	244508 KiB

sortbooks

#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 (stderr)

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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23