Submission #1298739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298739		rana_azka	Bouquet (EGOI24_bouquet)	C++20	100 / 100	94 ms	17192 KiB

Main

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

const int INF = 1e18;
const int MOD = 1e9+7;
const int MAXN = 2e5;

#define md ((lf+rg)/2)
#define lc (pos*2)
#define rc (pos*2+1)

int n, m;
int arr[MAXN+5][5];
int dp[MAXN+5];
int segtree[4*MAXN+5];

void mulaidarinol(){}

void update(int idx, int val, int lf, int rg, int pos){
    if(lf == rg){
        segtree[pos] = val;
        return ;
    }

    if(idx <= md) update(idx, val, lf, md, lc);
    else update(idx, val, md+1, rg, rc);

    segtree[pos] = max(segtree[lc], segtree[rc]);
}

int query(int ql, int qr, int lf, int rg, int pos){
    if(qr < lf || rg < ql) return 0;
    if(ql <= lf && rg <= qr) return segtree[pos];

    int ret = max(query(ql, qr, lf, md, lc), query(ql, qr, md+1, rg, rc));
    return ret;
}

void solve(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> arr[i][0] >> arr[i][1];

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for(int i = 1; i <= n; i++){
        while(!pq.empty() && pq.top().first < i){
            int idx = pq.top().second;
            update(idx, dp[idx], 1, n, 1);
            pq.pop();
        }

        int kiri = max(i - arr[i][0], 1ll);
        int kanan = min(i + arr[i][1], n);

        // cerr << i << " : " << kiri << ' ' << kanan << endl;

        if(kiri - 1 == 0) dp[i] = 1;
        else dp[i] = query(1, kiri - 1, 1, n, 1) + 1;

        pq.push({kanan, i});
    }

    int ans = 0;
    for(int i = 1; i <= n; i++) ans = max(dp[i], ans);

    cout << ans << endl;

    // for(int i = 1; i <= n; i++) cerr << dp[i] << ' ';
    // cerr << endl;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int tc = 1;
    // cin >> tc;
    while(tc--){
        // mulaidarinol();
        solve();
    }

    return 0;
}

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