Submission #420030

#TimeUsernameProblemLanguageResultExecution timeMemory
420030jamezzzFinancial Report (JOI21_financial)C++17
100 / 100
412 ms38708 KiB
#include <bits/stdc++.h> using namespace std; #define sf scanf #define pf printf #define fi first #define se second #define pb push_back #define INF 1023456789 #define all(x) x.begin(),x.end() typedef pair<int,int> ii; int n,d,p[300005],dp[300005],mn[300005],rt[300005]; deque<ii> dq; vector<ii> v; struct node{ int s,e,m,v; node *l,*r; node (int _s,int _e){ s=_s;e=_e;m=(s+e)/2;v=0; if(s!=e)l=new node(s,m),r=new node(m+1,e); } void up(int x,int nv){ if(s==x&&e==x){ v=nv;return; } if(x<=m)l->up(x,nv); else r->up(x,nv); v=max(l->v,r->v); } int qry(int x,int y){ if(s==x&&e==y)return v; if(y<=m)return l->qry(x,y); if(x>m)return r->qry(x,y); return max(l->qry(x,m),r->qry(m+1,y)); } }*root; int main(){ sf("%d%d",&n,&d); for(int i=0;i<n;++i){ sf("%d",&p[i]); while(!dq.empty()&&dq.back().fi>=p[i])dq.pop_back(); dq.push_back(ii(p[i],i)); while(dq.front().se<=i-d)dq.pop_front(); if(i>=d-1)mn[i]=dq.front().fi; else mn[i]=INF; } root=new node(0,n-1); while(!dq.empty())dq.pop_back(); for(int i=n-1;i>=0;--i){ while(!dq.empty()&&dq.front().fi<mn[i])dq.pop_front(); dq.push_front(ii(mn[i],i)); //if this is i+d, binary search to find p[i-d] if(i-d<0)break; if(dq.empty())rt[i-d]=n-1; else{ int lo=0,hi=dq.size()-1,mid,res=n-1; while(lo<=hi){ mid=(lo+hi)/2; if(dq[mid].fi<=p[i-d])lo=mid+1; else{ res=dq[mid].se;hi=mid-1; } } rt[i-d]=res; } } /* for(int i=0;i<n;++i)pf("%d ",mn[i]); pf("\n"); for(int i=0;i<n;++i)pf("%d ",rt[i]); pf("\n"); */ for(int i=0;i<n;++i){ v.pb(ii(p[i],-i)); } //sort in descending p[i] sort(all(v),greater<ii>()); for(int j=0;j<n;++j){ int i=-v[j].se; if(i+d>n-1){//can take anything after it dp[i]=root->qry(i,n-1)+1; root->up(i,dp[i]); continue; } dp[i]=root->qry(i,rt[i])+1; root->up(i,dp[i]); } int ans=0; for(int i=0;i<n;++i){ ans=max(ans,dp[i]); } pf("%d\n",ans); } /* 7 1 100 600 600 200 300 500 500 */

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:39:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  sf("%d%d",&n,&d);
      |    ^
Main.cpp:41:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   sf("%d",&p[i]);
      |     ^
#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...