oj.uz

Submission #504083

# Submission time Handle Problem Language Result Execution time Memory
504083 2022-01-09T17:15:23 Z Deepesson Zoltan (COCI16_zoltan) C++17
42 / 140
 343 ms 11196 KB 
#include <bits/stdc++.h>
#define MAX 205000

typedef std::pair<int,int> pii;

typedef std::pair<int,int*> pipo;

pii comb(pii a,pii b){
    if(a.first==b.first){
        return {a.first,a.second+b.second};
    }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 ;-;
**/
int main()
{
    pii base = {0,1};
    int N;
    std::cin>>N;
    int array[N]={};
    for(auto&x:array)std::cin>>x;
    {
        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;
        }
    }
    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=1;i!=MAX;++i){
        auto a = query(i,MAX-1,0);
        a=comb(a,base);
        auto b = query(0,i-1,1);
        b=comb(b,base);
        pii c = {a.first+b.first,a.second*b.second*(1<<(N-(a.first+b.first)))};
        best=std::max(best,c);
    }
    std::cout<<best.first<<" "<<best.second<<"\n";
}

Subtask #1
42.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 304 KB Output is correct
2 Correct 57 ms 336 KB Output is correct
3 Correct 60 ms 336 KB Output is correct
4 Correct 60 ms 300 KB Output is correct
5 Correct 60 ms 344 KB Output is correct
6 Correct 61 ms 352 KB Output is correct
7 Incorrect 61 ms 424 KB Output isn't correct
8 Incorrect 58 ms 336 KB Output isn't correct
9 Incorrect 69 ms 420 KB Output isn't correct
10 Incorrect 59 ms 412 KB Output isn't correct
11 Incorrect 227 ms 8484 KB Output isn't correct
12 Incorrect 208 ms 7520 KB Output isn't correct
13 Incorrect 200 ms 7116 KB Output isn't correct
14 Incorrect 255 ms 7940 KB Output isn't correct
15 Incorrect 291 ms 9616 KB Output isn't correct
16 Incorrect 343 ms 11196 KB Output isn't correct
17 Incorrect 281 ms 9152 KB Output isn't correct
18 Incorrect 280 ms 9124 KB Output isn't correct
19 Incorrect 286 ms 9144 KB Output isn't correct
20 Incorrect 269 ms 9176 KB Output isn't correct