제출 #1120930

#제출 시각아이디문제언어결과실행 시간메모리
1120930ezzzayBouquet (EGOI24_bouquet)C++14
0 / 100
100 ms9944 KiB
#include<bits/stdc++.h> using namespace std; #define itn long long #define int long long #define ff first #define ss second #define pb push_back const int N=3e5+5; int l[N],r[N]; int dp[N]; int st[4*N]; void update(int node, int L, int R, int idx, int val){ if(L==R){ st[node]=val; return; } int mid=(L+R)/2; if(L<=idx and idx<=mid)update(node*2,L,mid,idx,val); else update(node*2+1,mid+1,R,idx,val); st[node]=max(st[node*2],st[node*2+1]); } int find(int node, int L, int R, int l, int r){ if(l>r)return 0; if(l<=L and R<=r) return st[node]; if (l > R or r < L) return 0; int mid=(L+R)/2; return max(find(2*node,L,mid,l,r),find(2*node+1,mid+1,R,l,r)); } signed main(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>l[i]>>r[i]; } int ans=0; for(int i=1;i<=n;i++){ int p=find(1,1,n,1,max(1LL,i-l[i]-1)); dp[i]=max(dp[i],p+1); update(1,1,n,i,dp[i]); ans=max(ans,dp[i]); } cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...