Submission #1274933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274933		Robert_junior	Bouquet (EGOI24_bouquet)	C++20	100 / 100	108 ms	19056 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back  
#define all(x) x.begin(), x.end()
#define ins insert
#define F first
#define S second
const int N = 4e5 + 7, mod = 998244353;
int dp[N], f[N];
void upd(int idx, int val){
    for(; idx < N; idx |= (idx + 1)){
        f[idx] = max(f[idx], val);
    }
}
int get(int r){
    int res = 0;
    for(; r >= 0; r = (r & (r + 1)) - 1){
        res = max(res, f[r]);
    }
    return res;
}
void solve(){
	int n;
	cin>>n;
	vector<array<int, 3>>v;
	int l[n + 1], r[n + 1];
	int res = 0;
	multiset<array<int, 3>>s;
	for(int i = 1; i <= n; i++){
	    cin>>l[i]>>r[i];
	    l[i] = i - l[i];
	    r[i] = i + r[i];
	    while(s.size()){
	        array<int, 3>vl = *s.begin();
	        if(vl[0] < i){
	            upd(vl[1], vl[2]);
	            s.erase(s.begin());
	        }
	        else{
	            break;
	        }
	    }
	    dp[i] = max(dp[i], get(l[i] - 1) + 1); 
	    s.ins({r[i], i, dp[i]});
	    res = max(res, dp[i]);
	}
	cout<<res;
}
signed main(){
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
    //freopen("pieaters.in", "r", stdin);
    //freopen("pieaters.out", "w", stdout);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
}

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