oj.uz

Submission #504099

# Submission time Handle Problem Language Result Execution time Memory
504099 2022-01-09T18:31:08 Z Deepesson Zoltan (COCI16_zoltan) C++17
140 / 140
 322 ms 17124 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()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    ///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 336 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 588 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 229 ms 13704 KB Output is correct
12 Correct 184 ms 11960 KB Output is correct
13 Correct 169 ms 11324 KB Output is correct
14 Correct 236 ms 12020 KB Output is correct
15 Correct 292 ms 14904 KB Output is correct
16 Correct 322 ms 17124 KB Output is correct
17 Correct 259 ms 14540 KB Output is correct
18 Correct 260 ms 14668 KB Output is correct
19 Correct 262 ms 14652 KB Output is correct
20 Correct 269 ms 14644 KB Output is correct