제출 #1120945

#제출 시각아이디문제언어결과실행 시간메모리
1120945ezzzayBouquet (EGOI24_bouquet)C++14
100 / 100
221 ms46336 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=1e6+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<1 or r<1 or l>1e6 or r>1e6)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)); } vector<int>pst[N]; 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++){ for(auto a:pst[i]){ update(1,1,n,a,dp[a]); } dp[i]=find(1,1,n,1,i-l[i]-1)+1; pst[i+r[i]+1].pb(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...