제출 #530649

#제출 시각아이디문제언어결과실행 시간메모리
530649huangqrFinancial Report (JOI21_financial)C++14
19 / 100
737 ms63012 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<ld,ld> pd; typedef pair<ll,ll> pl; typedef pair<ll,pl> ppl; const ll lim=3e5+5,mod=1e9+7; ll par[lim],a[lim],dp[lim]; //Calced vals can be updated later. In a strict DP sense it would be dp(pos, time) rather than just dp(pos) ll fs(ll x){ if(x==par[x])return x; else return par[x]=fs(par[x]); } void mergeset(ll a,ll b){ a=fs(a),b=fs(b); if(a==b)return; par[a]=b; } struct node{ ll s,e,m,v=0,tomaxify=0; bool lazyflag=0,active=0; node *l,*r; node(ll ss,ll ee){ s=ss,e=ee,m=(s+e)/2; if(s==e)l=r=NULL; else l=new node(s,m),r=new node(m+1,e); } ll push(){ if(!active){ tomaxify=lazyflag=0; return v; } if(lazyflag){ v=max(v,tomaxify); if(s!=e){ if(l->active){ l->lazyflag=1; l->tomaxify=max(l->tomaxify,tomaxify); } if(r->active){ r->lazyflag=1; r->tomaxify=max(r->tomaxify,tomaxify); } } lazyflag=0; tomaxify=0; } return v; } void activate(ll pos,ll dpv){ push(); active=1; if(s==e&&s==pos)v=dpv; else if(pos<=m)l->activate(pos,dpv); else r->activate(pos,dpv); if(s!=e){ v=max(l->v,r->v); } } void maxify(ll a,ll b,ll maxifyval){ push(); if(!active)return; if(s==a&&e==b){ lazyflag=1; tomaxify=maxifyval; push(); } else if(b<=m)l->maxify(a,b,maxifyval); else if(a>m)r->maxify(a,b,maxifyval); else l->maxify(a,m,maxifyval),r->maxify(m+1,b,maxifyval); if(s!=e){ push(); v=max(l->push(),r->push()); } } ll query(ll a,ll b){ if(!active)return 0; push(); if(s==a&&e==b)return v; else if(b<=m)return l->query(a,b); else if(a>m)return r->query(a,b); else return max(l->query(a,m),r->query(m+1,b)); } }*root; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); ll n,d; cin>>n>>d; vector<pl>v; root=new node(0,n); for(int i=0;i<n;i++){ cin>>a[i]; par[i]=i; v.emplace_back(a[i],-i); } sort(v.begin(),v.end()); for(auto p:v){ ll i=-p.second; //dp[i]=max(1ll,dp[i]); //for(int j=max(i-d,0ll);j<i;j++)dp[i]=max(dp[i],dp[j]+1); if(i>0)dp[i]=1+root->query(max(i-d,0ll),i-1); else dp[i]=1; root->activate(i,dp[i]); ll t = fs(i); //t is the rightmost node to which we can push a dp-val update while(t < min(i+d,n-1)){ mergeset(t, t+1); t = fs(t); } if(i<n-1)root->maxify(i+1,max(i+t,n-1),dp[i]); //for(int j=i+1;j<=t;j++){ // if(dp[j])dp[j]=max(dp[j],dp[i]); //} //cout<<"after "<<i<<" (val "<<p.first<<"):\n"; //for(int i=0;i<n;i++)cout<<dp[i]<<" "; //cout<<"\n"; } cout<<root->query(n-1,n-1); 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...
#Verdict Execution timeMemoryGrader output
Fetching results...