Submission #1234073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234073		yixuan19	Bouquet (EGOI24_bouquet)	C++20	100 / 100	61 ms	20488 KiB

Main

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;

const int decalage = (1<<18);
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);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, l, r;
    cin >> N;
    int skipped = 0;
    int ans = 0;
    vector<pair<int,int> > tulips;
    vector<vector<pair<int,int> > > add (N*2);
    for (int i = 0; i < N; ++i){
        cin >> l >> r;
        tulips.push_back(make_pair(l,r));
    }
    int dp[N];
    int maxi = 0;
    for (int i = 0; i < N; ++i){
        dp[i] = 0;
    }
    
    for (int i = 0; i < N; ++i){
        // for (auto s: add){
        //     for (auto p: s){
        //         cout<<p.first<<' '<<p.second<<' ';
        //     }
        //     cout<<endl;
        // }
        if (add[i].size() > 0){
            for (auto p: add[i]){
                modify(p.first+decalage,dp[p.first]);
            }
        }
        // for (int i = decalage; i < decalage+N; ++i){
        //     cout<<tab[i]<<' ';
        // }
        // cout<<endl;
        
        // cout<<"querying "<<i<<" 0 to "<<max(i-tulips[i].first-1,0)<<endl;
        // cout<<"result "<<query(decalage,max(i-tulips[i].first-1,0) + decalage)<<endl;
        if (tab[decalage] != 0 && i-tulips[i].first-1 < 0){
            dp[i] = 1;
            continue;
        }
        dp [i] = query(decalage,max(0,i-tulips[i].first-1)+ decalage)  + 1;
        add[tulips[i].second + i +1].push_back(make_pair(i,dp[i]));
        // for (int i = 0; i < N; ++i){
        //     cout<<dp[i]<<' ';
        // }
        // cout<<endl;
        // cout<<endl;
    }

    maxi = 0;
    // for (int i = 0; i < N; ++i){
    //     cout<<dp[i]<<' ';
    // }
    // cout<<endl;
    for (int i = 0; i < N; ++i ){
        maxi = max(maxi, dp[i]);
    }
    cout<<maxi<<endl;
}

• Subtask 1: 8 / 8
• Subtask 2: 16 / 16
• Subtask 3: 28 / 28
• Subtask 4: 18 / 18
• Subtask 5: 30 / 30