Submission #1198539

#TimeUsernameProblemLanguageResultExecution timeMemory
1198539brover29Volontiranje (COCI21_volontiranje)C++17
0 / 110
258 ms589824 KiB
#include <bits/stdc++.h> //qwerty47924692 using namespace std; using ll = int; const ll N=1e6+1; const string br="617283"; #define sz(a)(ll)a.size() #define f first #define s second ll n,k,a[N],mx; pair<ll,ll>st[4*N],dp[N]; 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)); } queue<ll>q[N]; vector<vector<ll>>ans; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin>>n; for(ll i=1;i<=n;i++){ cin>>a[i]; dp[i]=get(1,1,n,1,a[i]-1); dp[i].f++; q[dp[i].f].push(i); update(1,1,n,a[i],{dp[i].f,i}); mx=max(mx,dp[i].f); } while(q[1].size()){ again:; if(q[1].empty())break; ll v=1; ll i=q[v].front(); // cout<<i<<' '; q[v].pop(); vector<ll>b; b.push_back(i); while(v!=mx){ v++; if(!q[v].size())goto again; ll j=q[v].front(); while(q[v].front()<i){ q[v].pop(); }if(a[q[v].front()]<a[i]){ v--; if(q[v].empty())goto again; i=q[v].front(); q[v].pop(); continue; } i=q[v].front(); // cout<<i<<' '; q[v].pop(); b.push_back(i); } ans.push_back(b); } cout<<ans.size()<<' '<<mx<<'\n'; for(auto vv:ans){ //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...