Submission #1148265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148265		Sir_Ahmed_Imran	Bouquet (EGOI24_bouquet)	C++17	100 / 100	48 ms	12176 KiB

Main

                //    01001100 01001111 01010100 01000001    \\
                //                                           \\
                //                ╦  ╔═╗╔╦╗╔═╗               \\
                //                ║  ║ ║ ║ ╠═╣               \\
                //                ╩═╝╚═╝ ╩ ╩ ╩               \\
                //                                           \\
                //    01001100 01001111 01010100 01000001    \\

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

#define N 200001
#define nl '\n'
#define ff first
#define ss second
#define add insert
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

int dp[N];
vector<pii> a[N];

int get(int x){
    int ans = 0; 
    while(x){
        ans = max(ans, dp[x]);
        x -= x & -x;
    }
    return ans;
}

void update(int x, int val){
    while(x < N){
        dp[x] = max(dp[x], val);
        x += x & -x;
    }
}

void solve(){
    int n, p, q;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> p >> q;
        q = min(n, i + q);
        p = max(0, i - p - 1);
        a[q].append({i, get(p) + 1});
        for(auto [j, k] : a[i])
            update(j, k);
    }
    cout << get(n);
}

int terminator(){
    L0TA;
    solve();
    return 0;
}

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