Submission #673982

#	Time	Username	Problem	Language	Result	Execution time	Memory
673982		kirakaminski968	Zoltan (COCI16_zoltan)	C++17	140 / 140	380 ms	19072 KiB

zoltan

#include <bits/stdc++.h>
#define MAX 205000
const long long MOD = 1e9+7;
typedef std::pair<long long,long long> pii;
typedef std::pair<int,int*> pipo;
pii comb(pii a,pii b){
    if(a.first==b.first){
        a.second%=(MOD*2);
        b.second%=(MOD*2);
        return {a.first,a.second+b.second%(MOD*2)};
    }else return std::max(a,b);
}
pii tab[MAX*4][2]={};
pii query(int l,int r,int x,int la=0,int ra=MAX-1,int pos=1){
    if(la>r||ra<l)return tab[0][x];
    if(la>=l&&ra<=r){
        return tab[pos][x];
    }
    int m = (la+ra)/2;
    return comb(query(l,r,x,la,m,pos*2),query(l,r,x,m+1,ra,(pos*2)+1));
}
void update(int t,pii k,int x,int la=0,int ra=MAX-1,int pos=1){
    if(la>t||ra<t)return;
    if(la==ra){
        tab[pos][x]=comb(tab[pos][x],k);
        return;
    }
    int m = (la+ra)/2;
    update(t,k,x,la,m,pos*2);
    update(t,k,x,m+1,ra,(pos*2)+1);
    tab[pos][x]=comb(tab[pos*2][x],tab[(pos*2)+1][x]);
}
long long binpow(long long a,long long b,long long c){
    long long r=1;
    while(b){
        if(b&1)r=(r*a)%c;
        b/=2;
        a=(a*a)%c;
    }
    return r;
}
int main()
{
    pii base = {0,1};
    int N;
    std::cin>>N;
    int array[N]={};
    for(auto&x:array)std::cin>>x;
    int curbesto=0;
    {
        std::vector<pipo> vec;
        for(auto&x:array)vec.push_back({x,&x});
        std::sort(vec.begin(),vec.end());
        int cur=3;
        int last=-1;
        for(auto&x:vec){
            if(x.first!=last){
                last=x.first;
                ++cur;
            }
            *(x.second)=cur;
        }
        curbesto=cur;
    }
    for(int i=N-1;i!=-1;--i){
        int x = array[i];
        auto resposta=query(x+1,MAX-1,0);
        resposta=comb(resposta,base);
        update(x,{resposta.first+1,resposta.second},0);
    }
    for(int i=N-1;i!=-1;--i){
        int x = array[i];
        auto resposta=query(0,x-1,1);
        resposta=comb(resposta,base);
        update(x,{resposta.first+1,resposta.second},1);
    }
    pii best={1,N};
    for(int i=4;i<curbesto+1;++i){
        auto a = query(i,MAX-1,0);
        a=comb(a,base);
        auto b = query(i-1,i-1,1);
        b=comb(b,base);
        pii c = {a.first+b.first,a.second*b.second};
        best=comb(best,c);
    }
    int menos=1;
    if(!(best.second&1)){
        menos=0;
        best.second/=2;
    }
    std::cout<<best.first<<" "<<((((best.second))*binpow(2,N-best.first-menos,MOD))%MOD)<< std::endl;
}

• Subtask 1: 140 / 140