𝗖𝗦 𝗔𝗹𝗴𝗼 💻 🌐 『𝗖𝗼𝗺𝗽𝗲𝘁𝗶𝘁𝗶𝘃𝗲 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴』

866 views08:37

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

const int MAXN = 1e5 + 5;

class SegmentTree {
private:
    vector<int> tree, lazy;
    int n;

    void build(int node, int start, int end) {
        if (start == end) {
            tree[node] = 0;
            return;
        }
        int mid = (start + end) / 2;
        build(2 * node, start, mid);
        build(2 * node + 1, mid + 1, end);
        tree[node] = max(tree[2 * node], tree[2 * node + 1]);
    }

    void push(int node, int start, int end) {
        if (lazy[node] != 0) {
            tree[node] += lazy[node];
            if (start != end) {
                lazy[2 * node] += lazy[node];
                lazy[2 * node + 1] += lazy[node];
            }
            lazy[node] = 0;
        }
    }

    void update(int node, int start, int end, int l, int r, int val) {
        push(node, start, end);
        if (start > r || end < l) return;
        if (l <= start && end <= r) {
            lazy[node] += val;
            push(node, start, end);
            return;
        }
        int mid = (start + end) / 2;
        update(2 * node, start, mid, l, r, val);
        update(2 * node + 1, mid + 1, end, l, r, val);
        tree[node] = max(tree[2 * node], tree[2 * node + 1]);
    }

    pair<int, int> query(int node, int start, int end, int l, int r) {
        push(node, start, end);
        if (start > r || end < l) return {-1, -1};
        if (l <= start && end <= r) return {tree[node], start};
        int mid = (start + end) / 2;
        pair<int, int> left = query(2 * node, start, mid, l, r);
        pair<int, int> right = query(2 * node + 1, mid + 1, end, l, r);
        if (left.first >= right.first) return left;
        return right;
    }

public:
    SegmentTree(int size) : n(size) {
        tree.resize(4 * n);
        lazy.resize(4 * n);
        build(1, 0, n - 1);
    }

    void update(int l, int r, int val) {
        update(1, 0, n - 1, l, r, val);
    }

    pair<int, int> query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }
};

void solve(int N, int Q, vector<vector<int>>& queries) {
    SegmentTree st(N + 1);

    for (const auto& query : queries) {
        int type = query[0];
        if (type == 1 || type == 2) {
            int L = query[1], R = query[2];
            st.update(L, R, 1);
        } else if (type == 3) {
            int C = query[1];
            pair<int, int> result = st.query(C, N);
            cout << result.second << '\n';
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int N, Q;
        cin >> N >> Q;

        vector<vector<int>> queries(Q);
        for (int i = 0; i < Q; ++i) {
            int type;
            cin >> type;
            if (type == 1 ) {
                int L=1, R;
                cin >> R;
                queries[i] = {type, L, R};
            }
            else if (type == 2) {
                int L, R=N;
                cin >> L ;
                queries[i] = {type, L, R};
            }
             else {
                int C;
                cin >> C;
                queries[i] = {type, C};
            }
        }

        solve(N, Q, queries);
    }

    return 0;
}

Maximum Product Sales ✅

👍2

1.02K views08:38