Submission #1236045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236045		yixuan19	Magic Tree (CEOI19_magictree)	C++20	11 / 100	65 ms	4280 KiB

magictree

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

const int decalage = (1<<20);
int tab[2*decalage];
void modify(int ind, int new_val){
    tab[ind] = new_val;
    while (ind > 1){
        ind/=2;
        tab[ind] = max(tab[ind*2], tab[ind*2+1]);
    }
}

int query(int l, int r){
    if (l == r) return tab[l];
    if (l%2 == 1){
        return max(tab[l], query(l+1,r));
    }
    if (r%2 == 0){
        return max(tab[r], query(l,r-1));
    }
    return query(l/2,r/2);
}

signed main(){
    int nb_vertices, nb_fruits, nb_max, parent;
    int location, day, juice;
    cin >> nb_vertices >> nb_fruits >> nb_max;
    for (int i = 2; i < nb_vertices+1; ++i){
        cin >> parent;
    }
    vector<pair<int,int> > fruits;
    int cnt = 0;
    for (int i = 0; i < nb_fruits; ++i){
        cin >> location >> day >> juice;
        if (day <= nb_max) fruits.push_back(make_pair(location,day));
    }
    sort(fruits.rbegin(), fruits.rend());
    // for (int i = 0; i < fruits.size(); ++i){
    //     cout<<fruits[i].first<<" "<<fruits[i].second<<" / ";
    // }
    // cout<<endl;
    int lis[fruits.size()];
    for (int i = 0; i < fruits.size(); ++i){
        lis[i] = 0;
    }
    lis[0] = 1;
    modify(fruits[0].second + decalage,1);
    for (int i = 1; i < fruits.size(); ++i){
        lis[i] = query(decalage,fruits[i].second+decalage) +1;
        modify(fruits[i].second+decalage,lis[i]);
        // for (int j = 0; j < fruits.size(); ++j){
        //     cout<<lis[j]<<" ";
        // }
        // cout<<endl;
    }
    for (int i = 0; i < fruits.size(); ++i){
        cnt = max(cnt, lis[i]);
    }
    cout<<cnt;
}

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