제출 #1267093

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1267093		GoBananas69	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	3093 ms	44764 KiB

sortbooks

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct SegmentTree {
    struct Node {
        int mx, sum;
        Node() : sum(0) {}
        Node(int _val) : sum(_val), mx(_val) {}
        Node(int _sum, int _mx) : sum(_sum), mx(_mx) {}
        Node operator+(const Node &b) { return Node(sum + b.sum, max(mx, b.mx)); }
    };
    int n;
    vector<int> nums;
    vector<Node> tree;
    int sum(int i, int L, int R, int l, int r) {
        if (L == l && r == R) {
            return tree[i].sum;
        }
        int m = (L + R) / 2;
        int x = 2 * i + 1, y = x + 1;
        if (r <= m) {
            return sum(x, L, m, l, r);
        } else if (l > m) {
            return sum(y, m + 1, R, l, r);
        } else {
            return sum(x, L, m, l, m) + sum(y, m + 1, R, m + 1, r);
        }
    }
    int mx(int i, int L, int R, int l, int r) {
        if (L == l && r == R) {
            return tree[i].mx;
        }
        int m = (L + R) / 2;
        int x = 2 * i + 1, y = x + 1;
        if (r <= m) {
            return mx(x, L, m, l, r);
        } else if (l > m) {
            return mx(y, m + 1, R, l, r);
        } else {
            return max(mx(x, L, m, l, m), mx(y, m + 1, R, m + 1, r));
        }
    }
    void update(int i, int L, int R, int p, int v) {
        if (L == R) {
            tree[i].sum = tree[i].sum + v;
            return;
        }
        int m = (L + R) / 2;
        int x = 2 * i + 1, y = x + 1;
        if (p <= m) {
            update(x, L, m, p, v);
        } else {
            update(y, m + 1, R, p, v);
        }
        tree[i] = tree[x] + tree[y];
    }
    void build(int i, int L, int R) {
        if (L == R) {
            tree[i] = Node(nums[L]);
            return;
        }
        int m = (L + R) / 2;
        int x = 2 * i + 1, y = x + 1;
        build(x, L, m);
        build(y, m + 1, R);
        tree[i] = tree[x] + tree[y];
    }
    SegmentTree(vector<int> &_nums) : n(_nums.size()), nums(_nums) {
        tree.assign(4 * n, Node());
        build(0, 0, n - 1);
    }
    int sum(int l, int r) { return sum(0, 0, n - 1, l, r); }
    int mx(int l, int r) { return mx(0, 0, n - 1, l, r); }
    void update(int p, int v) { update(0, 0, n - 1, p, v); }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int n, m;
    cin >> n >> m;
    vector<int> w(n);
    for (int &i : w) cin >> i;

    for (int _ = 0; _ < m; ++_) {
        int l, r, k;
        cin >> l >> r >> k;
        l--;
        r--;
        int len = r - l + 1;

        // d[a[i]] for uncompressed value of a[i]
        vector<int> a(len, 0), d(len);
        SegmentTree tree(a);
        for (int i = l; i <= r; ++i) {
            a[i - l] = w[i];
            d[i - l] = w[i];
        }
        sort(d.begin(), d.end());
        d.resize(unique(d.begin(), d.end()) - d.begin());
        for (int &i : a) i = lower_bound(d.begin(), d.end(), i) - d.begin();

        vector<int> inv(len);
        int ok = 0;
        for (int i = 0; i < len; ++i) {
            if (a[i] != len) inv[i] = tree.sum(a[i], len - 1);
            ok += inv[i];
            tree.update(a[i], 1);
        }
        if (ok == 0) {
            cout << "1\n";
            continue;
        }
        int mx = -1;
        int sum = 0;
        for (int i = 0; i < len; ++i) {
            mx = max(mx, d[a[i]]);
            if (inv[i] > 0) {
                sum = max(sum, d[a[i]] + mx);
            }
        }
        cout << (sum > k ? "0\n" : "1\n");
    }
}

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