Submission #1165504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165504		Tony1234	Bouquet (EGOI24_bouquet)	C++20	100 / 100	69 ms	16712 KiB

Main

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#ifdef _debug 
#include </home/tony/templates/debug.cpp>
#else
#define debug(...) 42
#endif

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define vi vector<int>
#define vt vector
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int MOD = 1e9 + 7, inf = (int)2e9;
const ll infll = (ll)1e18;

//credit usaco guide
//segment tree is 1 indexed
template<class T> struct SegTree {
	T U = -1e9; T F(T a, T b) { return max(a,b); }
	int N; vector<T> t; SegTree() {}
	SegTree(int N) : N(N), t(4*N,U) {}
	void upd(int I, T V) { upd(I,V,1,1,N); }
	void upd(int I, T V, int i, int l, int r) {
		if(l==r) { t[i]=max(t[i], V); return; } int m=(l+r)/2;
		if(I<=m) upd(I,V,i*2,l,m);
		else upd(I,V,i*2+1,m+1,r);
		t[i] = F(t[i*2], t[i*2+1]); }
	T qry(int L, int R) { return qry(L,R,1,1,N); }
	T qry(int L, int R, int i, int l, int r) {
		if(L<=l && r<=R) return t[i];
		if(R<l || L>r) return U; int m=(l+r)/2;
		return F(qry(L,R,i*2,l,m), qry(L,R,i*2+1,m+1,r)); }
};
void solve(){
    int N; cin >> N;
    vector<int> dp(N+1, 1); //dp[i] -> answer is i choose i as the last tulip
    vector<int> l(N+1), r(N+1);
    for(int i = 1; i <= N; i++)cin >> l[i] >> r[i];
    vector<vi> query(N+1); 
    for(int i = 1; i <= N; i++){
        if(i - l[i] - 1 >= 1){
            query[i - l[i] - 1].pb(i);
        }
    }
    SegTree<int> st(N+1); 
    for(int i = 1; i <= N; i++){
        if(i + r[i] <= N){
            st.upd(i + r[i], dp[i]); 
        }
        for(auto u : query[i]){
            dp[u] = max(dp[u], 1 + st.qry(1, u - 1)); 
        }
    }
    cout << *max_element(all(dp)) << '\n';
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    solve();
}

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