Submission #894037

#	Time	Username	Problem	Language	Result	Execution time	Memory
894037		Olympia	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	8 / 100	3059 ms	53884 KiB

sortbooks

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <cassert>
using namespace std;
struct Node {
    int mx;
    int mn;
    int val;
    Node () {
        this->mx = INT_MIN, this->mn = INT_MAX, this->val = 0;
    }
};
Node merge (Node left, Node right) {
    Node ans = Node();
    ans.mn = min(left.mn, right.mn);
    ans.mx = max(left.mx, right.mx);
    ans.val = max(left.val, right.val);
    if (left.mx > right.mn) {
        ans.val = max(ans.val, left.mx + right.mn);
    }
    return ans;
}
struct SegmentTree {
    vector<Node> vec;
    vector<int> nodes;
    Node query (int dum, int tl, int tr, int l, int r) {
        if (tl >= l && tr <= r) {
            return vec[dum];
        }
        if (tl > r || tr < l) {
            return {};
        }
        return merge(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) {
        return query(0, 0, (int)vec.size()/2 - 1, l, r).val;
    }
    Node build (int dum, int tl, int tr) {
        if (tl == tr) {
            vec[dum] = Node();
            vec[dum].mn = vec[dum].mx = this->nodes[tl];
            return vec[dum];
        }
        vec[dum] = merge(build(2 * dum + 1, tl, (tl + tr)/2), build(2 * dum + 2, (tl + tr)/2 + 1, tr));
        return vec[dum];
    }
    SegmentTree (vector<int> nodes) {
        this->nodes = nodes;
        int n = nodes.size();
        n = (1 << (int)log2(n)) * 2;
        vec.assign(2 * n, Node());
        while (this->nodes.size() < vec.size()) {
            this->nodes.push_back(0);
        }
        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--;
        int ans = 0;
        for (int i = l; i <= r; i++) {
            for (int j = i + 1; j <= r; j++) {
                if (v[i] > v[j]) {
                    ans = max(ans, v[i] + v[j]);
                }
            }
        }
        cout << (ans <= k) << '\n';
    }
}

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