Submission #864457

#	Time	Username	Problem	Language	Result	Execution time	Memory
864457		NeroZein	Zoltan (COCI16_zoltan)	C++17	140 / 140	305 ms	19152 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;


///The first number is the size of the sequence, and the second one the number of sequences

pii comb(pii a,pii b){

if(a.first==b.first){

    ///I'm multiplying MOD by two because I will divide by two later

    a.second%=(MOD*2);

    b.second%=(MOD*2);

    return {a.first,a.second+b.second%(MOD*2)};

}else return std::max(a,b);

}


///Basic seg3


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]);

}


///Binary exponentiation + Mod


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()

{

///You can always start an empty subsequence

pii base = {0,1};

int N;

std::cin>>N;

int array[N]={};

for(auto&x:array)std::cin>>x;

int curbesto=0;

///Coordinate Compression

{

    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;

}

///Longest decreasing subsequence (From end to start)

///Notice that if you reverse this sequence it's increasing

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);
    
}

///Longest increasing subsequence (From end to start)

///Notice that if you reverse this sequence it's decreasing

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);
    
}


///The idea is the following:

///You want the largest decreasing subsequence smaller than X (you will throw everything to the left)

///And the largest increasing subsequence greater or equal than X(You will throw to the right)

///The other N-(LIS.size) don't really matter, you can throw wherever you want.

///That's why we will use binary exponentiation


///Note:

///When I say increasing (or decreasing) I'm referring from the start (position 0) to the end (position N-1)


pii best={1,N};

//std::cout << "curbesto: " << curbesto << '\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);
    //std::cout << i << ' ' << a.first + b.first << ' ' << best.first << ' ' << best.second << '\n'; 
    //std::cout << i << ' ' << a.first << ' ' << a.second << ' ' << b.first << ' ' << b.second << '\n'; 
}


///The first element can't be thrown to the right nor left: It needs to be in the middle

///That's why we are dividing by two :)

int menos=1;

if(!(best.second&1)){

    menos=0;

    best.second/=2;

} else {
  assert(false); 
}

std::cout<<best.first<<" "<<((((best.second))*binpow(2,N-best.first-menos,MOD))%MOD)<<"\n";

}

• Subtask 1: 140 / 140