oj.uz

Submission #504098

# Submission time Handle Problem Language Result Execution time Memory
504098 2022-01-09T18:23:04 Z Deepesson Zoltan (COCI16_zoltan) C++17
140 / 140
 387 ms 17096 KB 
#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};
    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);
    }

    ///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;
    }
    std::cout<<best.first<<" "<<((((best.second))*binpow(2,N-best.first-menos,MOD))%MOD)<<"\n";
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 239 ms 13604 KB Output is correct
12 Correct 205 ms 11956 KB Output is correct
13 Correct 205 ms 11296 KB Output is correct
14 Correct 257 ms 12028 KB Output is correct
15 Correct 319 ms 14776 KB Output is correct
16 Correct 387 ms 17096 KB Output is correct
17 Correct 284 ms 14528 KB Output is correct
18 Correct 289 ms 14516 KB Output is correct
19 Correct 285 ms 14556 KB Output is correct
20 Correct 287 ms 14532 KB Output is correct