oj.uz

Submission #894095

# Submission time Handle Problem Language Result Execution time Memory
894095 2023-12-28T01:09:07 Z Olympia Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
8 / 100
 3000 ms 123940 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;
    int l;
    int r;
    Node (int l, int r) {
        this->mx = INT_MIN, this->mn = INT_MAX, this->val = 0, this->l = l, this->r = r;
    }
};
Node id = {-1, -1};
/*
struct MergeSortTree {
    vector<vector<int>> vec;
    vector<int> v;
    void build (int dum, int tl, int tr) {
        for (int i = tl; i <= tr; i++) {
            vec[dum].push_back(v[i]);
        }
        sort(vec[dum].begin(), vec[dum].end());
        if (tl == tr) {
            return;
        }
        build(2 * dum + 1, tl, (tl + tr)/2);
        build(2 * dum + 2, (tl + tr)/2 + 1, tr);
    }
    int get (vector<int>& arr, int k) {
        assert(!arr.empty());
        if (arr[0] > k) {
            return -INT_MAX;
        }
        int l = 0;
        int r = (int)arr.size() - 1;
        while (l != r) {
            int m = (l + r + 1)/2;
            if (arr[m] <= k) {
                l = m;
            } else {
                r = m - 1;
            }
        }
        return arr[l];
    }
    int query (int dum, int tl, int tr, int l, int r, int k) {
        if (tl >= l && tr <= r) {
            return get(vec[dum], k);
        }
        if (tl > r || l > tr) {
            return -INT_MAX;
        }
        return max(query(2 * dum + 1, tl, (tl + tr)/2, l, r, k), query(2 * dum + 2, (tl + tr)/2 + 1, tr, l, r, k));
    }
    int query (int l, int r, int k) {
        //find the largest element <= k in the range [l...r]
        //returns -INT_MAX if no such element is available
        return query(0, 0, (int)vec.size()/2 - 1, l, r, k);
    }
    MergeSortTree (vector<int> v) {
        assert(__builtin_popcount(v.size()) == 1);
        this->v = v;
        vec.resize(v.size() * 2);
        build(0, 0, (int)vec.size()/2 - 1);
    }
};
 */
struct SegmentTree {
    vector<Node> vec;
    vector<int> nodes;
    vector<vector<int>> values; //sorted list of values
    //MergeSortTree ms = MergeSortTree({0});
    Node merge (Node left, Node right) {
        if (left.l == -1) {
            return right;
        }
        if (right.l == -1) {
            return left;
        }
        assert(right.l == left.r + 1);
        Node ans = Node(left.l, right.r);
        ans.mn = min(left.mn, right.mn);
        ans.mx = max(left.mx, right.mx);
        ans.val = max(left.val, right.val);
        for (int i = left.l; i <= left.r; i++) {
            for (int j = right.l; j <= right.r; j++) {
                if (nodes[i] > nodes[j]) {
                    ans.val = max(ans.val, nodes[i] + nodes[j]);
                }
            }
        }
        return ans;
    }
    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 id;
        }
        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) {
        for (int i = tl; i <= tr; i++) {
            values[dum].push_back(nodes[i]);
        }
        sort(values[dum].begin(), values[dum].end());
        if (tl == tr) {
            vec[dum] = Node(tl, tr);
            vec[dum].mn = vec[dum].mx = nodes[tl];
            return vec[dum];
        }
        build(2 * dum + 1, tl, (tl + tr)/2);
        build(2 * dum + 2, (tl + tr)/2 + 1, tr);
        return vec[dum] = merge( build(2 * dum + 1, tl, (tl + tr)/2), build(2 * dum + 2, (tl + tr)/2 + 1, tr));
    }
    SegmentTree (vector<int> nodes) {
        this->nodes = nodes;
        int n = nodes.size();
        n = (1 << (int)log2(n)) * 2;
        this->values.resize(2 * n);
        vec.assign(2 * n, Node(0, 0));
        while (this->nodes.size() < vec.size()) {
            this->nodes.push_back((int)1e9);
        }
        //this->ms = MergeSortTree(this->nodes);
        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';
    }
}

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 53 ms 860 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 57 ms 1368 KB Output is correct
6 Correct 507 ms 2636 KB Output is correct
7 Correct 504 ms 2644 KB Output is correct
8 Correct 502 ms 2464 KB Output is correct
9 Correct 498 ms 2632 KB Output is correct
10 Correct 479 ms 2640 KB Output is correct

Subtask #2
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 53 ms 860 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 57 ms 1368 KB Output is correct
6 Correct 507 ms 2636 KB Output is correct
7 Correct 504 ms 2644 KB Output is correct
8 Correct 502 ms 2464 KB Output is correct
9 Correct 498 ms 2632 KB Output is correct
10 Correct 479 ms 2640 KB Output is correct
11 Execution timed out 3048 ms 8004 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3011 ms 123940 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3054 ms 21940 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
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 53 ms 860 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 57 ms 1368 KB Output is correct
6 Correct 507 ms 2636 KB Output is correct
7 Correct 504 ms 2644 KB Output is correct
8 Correct 502 ms 2464 KB Output is correct
9 Correct 498 ms 2632 KB Output is correct
10 Correct 479 ms 2640 KB Output is correct
11 Execution timed out 3048 ms 8004 KB Time limit exceeded
12 Halted 0 ms 0 KB -

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 53 ms 860 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 57 ms 1368 KB Output is correct
6 Correct 507 ms 2636 KB Output is correct
7 Correct 504 ms 2644 KB Output is correct
8 Correct 502 ms 2464 KB Output is correct
9 Correct 498 ms 2632 KB Output is correct
10 Correct 479 ms 2640 KB Output is correct
11 Execution timed out 3048 ms 8004 KB Time limit exceeded
12 Halted 0 ms 0 KB -