제출 #1235985

#제출 시각아이디문제언어결과실행 시간메모리
1235985clemmy14Magic Tree (CEOI19_magictree)C++20
0 / 100
45 ms8772 KiB
#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);
    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;
    // int ans=0;
    // for(int i=1; i<=n; i++) ans+=fruit[i].second;
    // cout << ans;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...