| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1360464 | hsuan._.0528 | Bouquet (EGOI24_bouquet) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn = 2e5+10;
int n;
int r[maxn], l[maxn];
vector<pair<int, int> > vec[maxn];
struct BIT{
int d[maxn]={};
int n;
void ins(int x, int v){
for(; x <= n; x += (x&-x)) d[x] = max(d[x], v);
}
int qq(int x){
int res = 0;
for(; x; x -= (x&-x)) sum = max(res, d[x]);
return res;
}
}bit;
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n;
bit.n = n;
for(int i=1; i<=n; i++) cin >> l[i]>>r[i];
int ans=0;
for(int i=1; i<=n; i++){
int now = bit.qq( max(0, i-l[i]-1) ) + 1;
ans = max(ans, now);
vec[ min(n+1, i+r[i]) ].push_back( {i, now} );
for(auto[pos, val]: vec[i]) bit.ins(pos, val);
}
cout<<ans;
return 0;
}