제출 #894204

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
894204		Olympia	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	77 / 100	3050 ms	259648 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 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);
            return;
        }
        if (tl > r || tr < l) {
            return;
        }
        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]};
            return;
        }
        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]);
        int l = 0;
        int r = 0;
        while (l < vec[2 * dum + 1].v.size() || r < vec[2 * dum + 2].v.size()) {
            if (l == vec[2 * dum + 1].v.size()) {
                vec[dum].v.push_back(vec[2 * dum + 2].v[r++]);
            } else if (r == vec[2 * dum + 2].v.size()) {
                vec[dum].v.push_back(vec[2 * dum + 1].v[l++]);
            } else if (vec[2 * dum + 1].v[l] < vec[2 * dum + 2].v[r]){
                vec[dum].v.push_back(vec[2 * dum + 1].v[l++]);
            } else {
                vec[dum].v.push_back(vec[2 * dum + 2].v[r++]);
            }
        }
    }
    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((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';
    }
}

컴파일 시 표준 에러 (stderr) 메시지

sortbooks.cpp: In member function 'int SegmentTree::query(int, int)':
sortbooks.cpp:59:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for (int i = 1; i < intervals.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~
sortbooks.cpp: In member function 'void SegmentTree::build(int, int, int)':
sortbooks.cpp:75:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         while (l < vec[2 * dum + 1].v.size() || r < vec[2 * dum + 2].v.size()) {
      |                ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:75:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         while (l < vec[2 * dum + 1].v.size() || r < vec[2 * dum + 2].v.size()) {
      |                                                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:76:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             if (l == vec[2 * dum + 1].v.size()) {
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:78:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |             } else if (r == vec[2 * dum + 2].v.size()) {
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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