Submission #1235987

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235987		clemmy14	Magic Tree (CEOI19_magictree)	C++20	0 / 100	46 ms	8772 KiB

magictree

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int INF=1e9;
struct SegTreeMax {
    int n; vector<int> s;
    SegTreeMax(int n) : s(2*n), n(n) {}
    void update(int pos, int val) {
        for(s[pos+=n]=val; pos/=2;) {
            s[pos]=max(s[pos*2], s[pos*2+1]);
        }
    }
    int query(int b, int e) {
        int ra=-INF, rb=-INF;
        for(b+=n, e+=n; b<e; b/=2, e/=2) {
            if(b%2) ra=max(ra, s[b++]);
            if(e%2) rb=max(rb, s[--e]);
        }
        return max(ra, rb);
    }
};

//vector<pair<int, int>> fruit;
vector<vector<int>> adj;

signed main() {
    int n, m, k; cin >> n >> m >> k;
    adj = vector<vector<int>>(n+1);
    for(int i=1; i<n; i++) {
        int a; cin >> a;
        adj[i+1].push_back(a);
        adj[a].push_back(i+1);
    }
    vector<int> fruit(n+1, -1);
    //fruit = vector<pair<int, int>>(n+1, {0, 0});
    for(int i=0; i<k; i++) {
        int v, d, w; cin >> v >> d >> w;
        fruit[v]=d;
        //fruit[v]={d, w};
    }
    SegTreeMax segmax(k+1);
    int ans=0;
    for(int i=1; i<=n; i++) if(fruit[i] != -1) {
        int nbLar=segmax.query(fruit[i], k);
        int newVal=max(segmax.query(fruit[i], fruit[i]+1), nbLar+1);
        segmax.update(fruit[i], newVal);
        ans=max(ans, newVal);
        // for(int j=1; j<=n; j++) cout << segmax.query(j, j+1) << ' ';
        // cout << endl;
    }
    cout << ans;
    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 3
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17