제출 #1088182

#제출 시각아이디문제언어결과실행 시간메모리
1088182AlmontherBouquet (EGOI24_bouquet)C++98
0 / 100
47 ms8988 KiB
#include <bits/stdc++.h> #define suiii ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define ll long long #define co cout<< //#pragma GCC optimize("O3,Ofast,unroll-loops") //#pragma GCC target("avx2,sse3,sse4,avx") using namespace std; //stuff const ll N=exp2(ceil(log2(2e5))); ll tre[N*4],n,dp[1000001],l[1000001],r[1000001]; ll mxof(ll l,ll r,ll i,ll lq,ll rq){ if(l>rq||r<lq) return 0; if(l>=lq&&r<=rq) return tre[i]; ll mid=(l+r)/2; return max(mxof(l,mid,i*2,lq,rq),mxof(mid+1,r,i*2+1,lq,rq)); } void solve(){ ll n; cin>>n; for(ll i=0;i<n;i++){ cin>>l[i]>>r[i]; l[i]=min(i,l[i]); r[i]=min(n-i-1,r[i]); } dp[0]=0; ll mx=0; priority_queue<pair<ll,ll>>q; for(int i=0;i<n;i++){ while(q.size()&&-q.top().first<i){ ll idx=q.top().second+N; q.pop(); tre[idx]=max(tre[idx],dp[idx-N]); idx/=2; while(idx){ tre[idx]=max(tre[idx*2],tre[idx*2+1]); idx/=2; } } if(i-l[i]==0){ q.push({-(i+r[i]),i}); continue; } dp[i]=mxof(0,N-1,1,0,i-l[i])+1; mx=max(mx,dp[i]); q.push({-(i+r[i]),i}); } co mx; } int main() { suiii int _=1; // cin>>_; while(_--) solve(); return 0; }
#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...