제출 #1360588

#제출 시각아이디문제언어결과실행 시간메모리
1360588hsuan._.0528Bouquet (EGOI24_bouquet)C++20
100 / 100
34 ms13728 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))  res = 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;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…