Submission #372326

#	Time	Username	Problem	Language	Result	Execution time	Memory
372326		gustason	Airplanes (LMIO17_lektuvai)	C++11	51 / 100	91 ms	12780 KiB

lektuvai

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
struct SegTree {
    int n;
    vector<int> tree;
    SegTree(vector<int>& a) {
        n = a.size();
        tree.assign(2*n, 0);
        for(int i = n; i < 2*n; i++) {
            tree[i] = a[i-n];
        }
        for(int idx = n-1; idx > 1; idx--) {
            tree[idx] = max(tree[2*idx], tree[2*idx+1]);
        }
    }
    void update(int idx, int val) {
        idx += n;
        tree[idx] = val;
        while(idx > 1) {
            idx /= 2;
            tree[idx] = max(tree[2*idx], tree[2*idx+1]);
        }
    }
    int getmax(int l, int r) {
        l += n, r += n;
        int mx = 0;

        while(l < r) {
            if (l % 2) {
                mx = max(mx, tree[l]);
                l++;
            }
            if (r % 2) {
                r--;
                mx = max(mx, tree[r]);
            }
            l /= 2, r /= 2;
        }

        return mx;
    }
};
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> p(n), r(n, -1);
//    iota(r.begin(), r.end(), 0);
    p[n-1] = -1;
    for(int i = 0; i < n-1; i++) {
        cin >> p[i];
        p[i]--;
        r[p[i]] = i;
    }

    if (n <= 1000) {
        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 {
    SegTree tree(a);
    int q;
    cin >> q;
    while(q--) {
        char type;
        cin >> type;
        if (type == 'I') {
            int idx;
            cin >> idx;
            idx--;
            int ans;
            if (r[idx] == -1) {
                ans = tree.getmax(idx, idx+1);
            } else {
                ans = max(tree.getmax(0, r[idx]+1), tree.getmax(idx, idx+1));
            }
            cout << ans << "\n";
        } else {
            int idx, val;
            cin >> idx >> val;
            idx--;
            tree.update(idx, max(tree.getmax(0, r[idx]+1), tree.getmax(idx, idx+1)) + val);
        }
    }
    }
//    for(int i = 0; i < n; i++) {
//        cout << r[i] << " ";
//    }
    return 0;
}

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