Submission #939436

#TimeUsernameProblemLanguageResultExecution timeMemory
939436WarinchaiZoltan (COCI16_zoltan)C++14
70 / 140
316 ms35192 KiB
#include<bits/stdc++.h> #define int long long using namespace std; int ar[200005]; int md=1e9+7; struct node{ int l,w; node(int a=0,int b=1){ l=a,w=b; } friend node operator+(node a,node b){ node c; c.l=max(a.l,b.l); c.w=a.l==b.l?a.w+b.w:a.l>b.l?a.w:b.w; if(c.l==0)c.w=1; c.w%=md; return c; } }; struct segtree{ node info[800005]; void upd(int st,int en,int i,int pos,int len,int way){ if(st>pos||en<pos)return; if(st==en)return void(info[i]=info[i]+node(len,way)); int m=(st+en)/2; upd(st,m,i*2,pos,len,way); upd(m+1,en,i*2+1,pos,len,way); info[i]=info[i*2]+info[i*2+1]; } node fans(int st,int en,int i,int l,int r){ if(st>r||en<l)return node(); if(st>=l&&en<=r)return info[i]; int m=(st+en)/2; return fans(st,m,i*2,l,r)+fans(m+1,en,i*2+1,l,r); } }lis,lds; node inc[200005]; node de[200005]; node ans; vector<int>v; int binpow(int a,int b){ if(b==0)return 1; if(b==1)return a; if(b%2==0)return (binpow(a,b/2)*binpow(a,b/2))%md; return (binpow(a,b/2)*binpow(a,b/2)*a)%md; } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n;cin>>n; for(int i=1;i<=n;i++)cin>>ar[i],v.push_back(ar[i]); sort(v.begin(),v.end()); int id=0; for(int i=n;i>=1;i--){ id=lower_bound(v.begin(),v.end(),ar[i])-v.begin()+1; inc[i]=lds.fans(1,n,1,id+1,n); inc[i].l+=1; de[i]=lis.fans(1,n,1,1,id-1); de[i].l+=1; //cerr<<id<<":\n"; //cerr<<inc[i].l<<" "<<inc[i].w<<"\n"; //cerr<<de[i].l<<" "<<de[i].w<<"\n\n"; lis.upd(1,n,1,id,de[i].l,de[i].w); lds.upd(1,n,1,id,inc[i].l,inc[i].w); } //cerr<<"\n"; //cerr<<"\n"; int left,way,l; node temp; for(int i=1;i<=n;i++){ left=n-(inc[i].l+de[i].l)+1; //cerr<<"left:"<<left<<"\n"; way=binpow(2,left); way=(way*inc[i].w*de[i].w)%md; l=inc[i].l+de[i].l-1; temp=node(l,way); //cerr<<l<<" "<<way<<"\n"; ans=ans+temp; } cout<<ans.l<<" "<<ans.w; }
#Verdict Execution timeMemoryGrader output
Fetching results...