제출 #372322

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
372322		gustason	Airplanes (LMIO17_lektuvai)	C++11	45 / 100	93 ms	8648 KiB

lektuvai

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
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;
    }
};
int 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;
    }

    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: 0 / 6
• Subtask 3: 40 / 40
• Subtask 4: 0 / 49