제출 #1309558

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309558		Newtonabc	Bouquet (EGOI24_bouquet)	C++20	100 / 100	162 ms	15896 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int N=1<<19;
int l[N],r[N],s[N],dp[N];
vector<pair<int,int>> upd[N];
void update(int l,int r,int idx,int a,int b){
    if(a<l || a>r) return;
    if(l==r){
        s[idx]=b;
        return;
    }
    int m=(l+r)/2;
    update(l,m,idx*2,a,b);
    update(m+1,r,idx*2+1,a,b);
    s[idx]=max(s[idx*2],s[idx*2+1]);
}
int query(int l,int r,int idx,int a,int b){
    if(b<l || a>r) return INT_MIN;
    if(a<=l && b>=r) return s[idx];
    int m=(l+r)/2;
    return max(query(l,m,idx*2,a,b),query(m+1,r,idx*2+1,a,b));
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>l[i] >>r[i],l[i]=min(l[i],i-1),r[i]=min(r[i],n-i);
    for(int i=1;i<=n;i++){
        for(auto [ind,val]:upd[i]){
            update(0,n+1,1,ind,val);
        }
        dp[i]=query(0,n+1,1,0,i-l[i]-1)+1;
        upd[i+r[i]+1].push_back({i,dp[i]});
    }
    cout<<*max_element(dp+1,dp+n+1);
}

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