Submission #1267151

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267151		GoBananas69	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	8 / 100	3097 ms	46508 KiB

sortbooks

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

struct SegmentTree {
    struct Node {
        int mx, sum;
        Node() : mx(0), sum(0) {}
        Node(int _val) : mx(_val), sum(_val) {}
        Node(int _sum, int _mx) : sum(_sum), mx(_mx) {}
        Node operator+(const Node &b) const { 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 > r) return 0;
        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 > r) return -INT_MAX;
        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 += 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 * max(1, n), Node());
        if (n > 0) build(0, 0, n - 1);
    }
    int sum(int l, int r) {
        if (l > r) return 0;
        return sum(0, 0, n - 1, l, r);
    }
    int mx(int l, int r) {
        if (l > r) return -INT_MAX;
        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;
    if (!(cin >> n >> m)) return 0;
    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;
        vector<int> a(len), d(len);
        for (int i = l; i <= r; ++i) {
            a[i - l] = w[i];
            d[i - l] = w[i];
        }
        sort(d.begin(), d.end());
        d.erase(unique(d.begin(), d.end()), d.end());
        for (int &x : a) x = lower_bound(d.begin(), d.end(), x) - d.begin();
        int D = (int)d.size();
        SegmentTree tree(vector<int>(D, 0));

        vector<int> inv(len, 0);
        long long ok = 0;
        for (int i = 0; i < len; ++i) {
            if (a[i] + 1 <= D - 1) inv[i] = tree.sum(a[i] + 1, D - 1);
            else inv[i] = 0;
            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");
    }
    return 0;
}

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