Submission #1198098

#TimeUsernameProblemLanguageResultExecution timeMemory
1198098brover29Volontiranje (COCI21_volontiranje)C++17
0 / 110
0 ms328 KiB
#include <bits/stdc++.h> //qwerty47924692 using namespace std; using ll = int; const ll N=1e6+29; const string br="617283"; #define sz(a)(ll)a.size() #define f first #define s second ll n,k,a[N],nxt[N],prv[N],s,f,p[N]; pair<ll,ll>st[4*N],dp[N]; vector<vector<ll>>v; ll mx=0; void update(ll v,ll l,ll r,ll pos,pair<ll,ll> x){ if(l==r){ st[v]=x; return; } ll mid=(r+l)>>1; if(pos<=mid)update(v*2,l,mid,pos,x); else update(v*2+1,mid+1,r,pos,x); st[v]=max(st[v*2],st[v*2+1]); } pair<ll,ll> get(ll v,ll l,ll r,ll x,ll y){ if(l>y||x>r||x>y)return {0,0}; if(x<=l&&r<=y)return st[v]; ll mid=(r+l)>>1; return max(get(v*2,l,mid,x,y),get(v*2+1,mid+1,r,x,y)); }bool cmp(ll i,ll j){ return a[i]<a[j]; } void calc(){ for(ll i=n;i>=1;i--){ if(dp[i].f==mx){ vector<ll>b; ll j=i; while(i!=0){ b.push_back(i); i=dp[i].s; } v.push_back(b); i=j; } } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin>>n; for(ll i=1;i<=n;i++){ cin>>a[i]; p[i]=i; }sort(p+1,p+1+n,&cmp); for(ll j=1;j<=n;j++){ ll i=p[j]; assert(a[p[j]]>a[p[j-1]]); // cout<<i<<' '; dp[i]=get(1,0,n,1,i-1); dp[i].f++; mx=max(mx,dp[i].f); update(1,0,n,dp[i].s,{0,0}); update(1,0,n,i,{dp[i].f,i}); } calc(); cout<<v.size()<<' '<<mx<<'\n'; for(auto vv:v){ reverse(vv.begin(),vv.end()); for(ll i:vv){ cout<<i<<' '; } cout<<'\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...