oj.uz

Submission #504094

# Submission time Handle Problem Language Result Execution time Memory
504094 2022-01-09T18:04:17 Z Deepesson Zoltan (COCI16_zoltan) C++17
119 / 140
 389 ms 17192 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*2);
        b.second%=(MOD*2);
        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 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 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 3 ms 512 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Incorrect 248 ms 13708 KB Output isn't correct
12 Incorrect 202 ms 11952 KB Output isn't correct
13 Incorrect 195 ms 11296 KB Output isn't correct
14 Correct 264 ms 11964 KB Output is correct
15 Correct 333 ms 14832 KB Output is correct
16 Correct 389 ms 17192 KB Output is correct
17 Correct 299 ms 14672 KB Output is correct
18 Correct 309 ms 14540 KB Output is correct
19 Correct 308 ms 14672 KB Output is correct
20 Correct 324 ms 14620 KB Output is correct