Submission #939446

#	Time	Username	Problem	Language	Result	Execution time	Memory
939446		Warinchai	Zoltan (COCI16_zoltan)	C++14	77 / 140	284 ms	33268 KiB

zoltan

#include<bits/stdc++.h>
using namespace std;
int ar[200005];
int md=1e9+7;
struct node{
    int l;
    long long 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;
long long 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";
    long long 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;
}

• Subtask 1: 77 / 140