oj.uz

Submission #504092

# Submission time Handle Problem Language Result Execution time Memory
504092 2022-01-09T18:02:47 Z Deepesson Zoltan (COCI16_zoltan) C++17
119 / 140
 383 ms 17092 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;

pii comb(pii a,pii b){
    if(a.first==b.first){
        a.second%=MOD;
        b.second%=MOD;
        assert(a.second+b.second<MOD*MOD);
        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]);
}
/**
    Tamanho e numero da sequencia crescente maior ou igual a x
    Significa que o menor numero da sequencia deve ser maior ou igual a x
    Solucao: Comecar do final e computar uma sequencia estritamente decrescente, o ultimo valor sera o menor.

    Tamanho e numero da sequencia decrescente menor que x
    Solucao: Do fim ao inicio computar uma sequencia estritamente crescente, no final eh soh consultar o maior numero.

    Depois de computar:
    Checar para todo x valido a resposta, imprimir o maior :)
    Problema: Contar numero de sequencias ;-;
**/
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={0,0};
    for(int i=3;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<<best.first<<" "<<((((best.second/2))*binpow(2,N-best.first,MOD))%MOD)<<"\n";
}

Subtask #1
119.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 1 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 3 ms 460 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Incorrect 248 ms 13616 KB Output isn't correct
12 Incorrect 214 ms 11992 KB Output isn't correct
13 Incorrect 203 ms 11188 KB Output isn't correct
14 Correct 279 ms 11956 KB Output is correct
15 Correct 367 ms 14864 KB Output is correct
16 Correct 383 ms 17092 KB Output is correct
17 Correct 321 ms 14624 KB Output is correct
18 Correct 302 ms 14556 KB Output is correct
19 Correct 307 ms 14692 KB Output is correct
20 Correct 292 ms 14556 KB Output is correct