Submission #372284

#	Time	Username	Problem	Language	Result	Execution time	Memory
372284		gustason	Airplanes (LMIO17_lektuvai)	C++11	11 / 100	59 ms	6636 KiB

lektuvai

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct Node {
    int mx;
    int setAll;
    bool setAllValid;
    Node() {
        setAllValid = false;
        setAll = 0;
        mx = 0;
    }
    void Reset() {
        setAllValid = false;
    }
};
struct SegTree {
    int n;
    vector<Node> tree;
    SegTree(vector<int>& a) {
        n = a.size();
        tree.assign(4*n, Node());
        build_r(a, 0, n-1, 0);
    }
    void build_r(vector<int>& a, int l, int r, int idx) {
        if (l == r) {
            if (l < n)
                tree[idx].mx = a[l];
            else
                tree[idx].mx = 0;
            return;
        }

        int mid = (l + r) / 2;
        build_r(a, l, mid, 2*idx+1);
        build_r(a, mid+1, r, 2*idx+2);

        tree[idx].mx = max(tree[2*idx+1].mx, tree[2*idx+2].mx);
    }
    void applyAggr(int idx, int l, int r) {
        if (tree[idx].setAllValid)
            tree[idx].mx = max(tree[idx].mx, tree[idx].setAll);

        if (l != r) {
            compose(idx, 2*idx+1);
            compose(idx, 2*idx+2);
        }

        tree[idx].Reset();
    }
    void compose(int par, int child) {
        if (tree[par].setAllValid) {
            tree[child].setAllValid = true;
            tree[child].setAll = tree[par].setAll;
        }
    }
    void updateSet(int L, int R, int val) {
        updateSet_r(0, 0, n-1, L, R, val);
    }
    void updateSet_r(int idx, int l, int r, int& L, int& R, int& val) {
        if (r < L || R < l || l >= n)
            return;
        if (L <= l && R >= r) {
            tree[idx].setAllValid = true;
            tree[idx].setAll = max(tree[idx].setAll, val);
            return;
        }

        applyAggr(idx, l, r);

        int mid = (l + r) / 2;
        updateSet_r(2*idx+1, l, mid, L, R, val);
        updateSet_r(2*idx+2, mid+1, r, L, R, val);
        applyAggr(2*idx+1, l, mid);
        applyAggr(2*idx+2, mid+1, r);

        tree[idx].mx = max(tree[2*idx+1].mx, tree[2*idx+2].mx);
    }
    int getMax(int L, int R) {
        return getMax_r(0, 0, n-1, L, R);
    }
    int getMax_r(int idx, int l, int r, int& L, int& R) {
        if (r < L || R < l || l >= n)
            return 0;

        applyAggr(idx, l, r);

        if (L <= l && R >= r)
            return tree[idx].mx;

        int mid = (l + r) / 2;
        return max(getMax_r(2*idx+1, l, mid, L, R), getMax_r(2*idx+2, mid+1, r, L, R));
    }
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("test.in", "r", stdin);
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> p(n);
    p[n-1] = -1;
    for(int i = 0; i < n-1; i++) {
        cin >> p[i];
        p[i]--;
    }
    if (n <= 2000) {
        int q;
        cin >> q;
        for(int i = 0; i < q; i++) {
            char type;
            cin >> type;
            if (type == 'I') {
                int idx;
                cin >> idx;
                idx--;
                cout << a[idx] << "\n";
            } else if (type == 'P') {
                int idx, by;
                cin >> idx >> by;
                idx--;
                a[idx] += by;
                vector<bool> vis(n+1, false);
                while(1) {
                    int par = p[idx];
                    if (par == -1 || vis[par]) break;
                    a[par] = max(a[par], a[idx]);
                    idx = par;
                }
            }
        }
    } else {
    int q;
    cin >> q;
    SegTree tree(a);
    for(int i = 0; i < q; i++) {
        char type;
        cin >> type;
        if (type == 'I') {
            int idx;
            cin >> idx;
            idx--;
            cout << tree.getMax(0, idx) << "\n";
        } else if (type == 'P') {
            int idx, by;
            cin >> idx >> by;
            idx--;
            a[idx] = tree.getMax(0, idx) + by;
            tree.updateSet(idx, n, a[idx]);
        }
    }
    }
//    vector<int> a(4);
//    a = {2, 4, 5, 5};
//    SegTree tree(a);
//    tree.updateSet(0, 2, 8);
//    tree.updateSet(0, 3, 6);
//    tree.updateSet(0, 3, 4);
//    tree.updateSet(0, 3, 7);
//    tree.updateSet(0, 1, 9);
//    for(int i = 0; i < 4; i++) {
//        cout << tree.getMax(i, i) << " ";
//    } cout << "\n";
//    cout << tree.getMax(2, 3) << "\n";
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 0 / 40
• Subtask 4: 0 / 49