Submission #787074

#	Time	Username	Problem	Language	Result	Execution time	Memory
787074		Ahmed57	Zoltan (COCI16_zoltan)	C++17	105 / 140	401 ms	34828 KiB

zoltan

#include<bits/stdc++.h>
#include<queue>
using namespace std;
long long n;long long arr[200005];
long long mod = 1000000007;
struct node{
    long long ma,cnt;
}seg[800001],em;
node combine(node a,node b){
    node ans;
    ans.ma = max(a.ma,b.ma);
    if(a.ma==b.ma)ans.cnt = (a.cnt+b.cnt)%mod;
    if(a.ma>b.ma)ans.cnt = a.cnt;
    if(b.ma>a.ma)ans.cnt = b.cnt;
    return ans;
}
void build(int p,int l,int r){
    if(l==r){
        seg[p] = em;
        return ;
    }
    int md = (l+r)/2;
    build(p*2,l,md);build(p*2+1,md+1,r);
    seg[p] = combine(seg[p*2],seg[p*2+1]);
}
void update(int p,int l,int r,int idx,pair<long long,long long> val){
    if(l==r){
        if(val.first>seg[p].ma){
            seg[p].ma = val.first;
            seg[p].cnt = val.second;
        }else if(val.first==seg[p].ma){
            seg[p].cnt += val.second;
        }
        return ;
    }int md = (l+r)/2;
    if(idx<=md)update(p*2,l,md,idx,val);
    else update(p*2+1,md+1,r,idx,val);
    seg[p] = combine(seg[p*2],seg[p*2+1]);
}
node query(int p,int l,int r,int lq,int rq){
    if(l>rq||r<lq||l>r)return em;
    if(l>=lq&&r<=rq)return seg[p];
    int md = (l+r)/2;
    return combine(query(p*2,l,md,lq,rq),query(p*2+1,md+1,r,lq,rq));
}
int main(){
    em.ma = -1 , em.cnt = 1;
    cin>>n;
    for(int i = 0;i<n;i++){
        cin>>arr[i];arr[i]++;
    }
    arr[n] = 1;
    map<int,int> comp,sav;
    for(int i = 0;i<=n;i++)comp[arr[i]]++;
    int z = 0;
    for(auto i:comp){
        sav[i.first] = ++z;
    }
    for(int i = 0;i<=n;i++)arr[i] = sav[arr[i]];
    build(1,1,z);
    node dpr[n+1];
    for(int i = n;i>=0;i--){
        if(i==n){
            dpr[i].ma = 0 , dpr[i].cnt = 1;
        }else{
            dpr[i] = query(1,1,z,1,arr[i]-1);
            dpr[i].ma ++;
            //dpr[i] = combine(dpr[i+1],dpr[i]);
            //cout<<dpr[i].cnt<<" "<<dpr[i].ma<<endl;
        }
        update(1,1,z,arr[i],make_pair(dpr[i].ma,dpr[i].cnt));
    }
    node dpl[n+1];
    build(1,1,z);
    for(int i =1;i<n;i++){
        update(1,1,z,arr[i-1],make_pair(dpr[i-1].ma,dpr[i-1].cnt));
        dpl[i] = query(1,1,z,1,arr[i]-1);
        dpl[i].ma ++;
        //cout<<dpl[i].ma<<endl;
        //if(i>1)dpl[i] = combine(dpl[i-1],dpl[i]);
        //else dpl[i] = combine(dpr[0],dpl[i]);
        update(1,1,z,arr[i],make_pair(dpl[i].ma,dpl[i].cnt));
    }
    long long xd = 1;
    long long mi = -1 , su = 0;
    for(int i = 0;i<n;i++){
        if(mi<dpr[i].ma){
            mi = dpr[i].ma;
            su = 0;
        }if(mi==dpr[i].ma){
            su+=dpr[i].cnt;
        }
    }
    for(int i = 1;i<n;i++){
        if(mi<dpl[i].ma){
            mi = dpl[i].ma;
            su = 0;
        }if(mi==dpl[i].ma){
            su+=dpl[i].cnt;
        }
    }
    for(int i = 0;i<n-mi;i++){
        xd*=2;xd%=mod;
    }
    cout<<mi<<" "<<(su*xd)%mod<<endl;
}

• Subtask 1: 105 / 140