oj.uz

Submission #504089

# Submission time Handle Problem Language Result Execution time Memory
504089 2022-01-09T18:01:01 Z Deepesson Zoltan (COCI16_zoltan) C++17
112 / 140
 379 ms 17104 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.second<<"\n";
  //  std::cout<<binpow(2,N-best.first,MOD)<<"\n";
    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
112.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 Incorrect 0 ms 332 KB Output isn't 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 332 KB Output is correct
11 Incorrect 242 ms 13616 KB Output isn't correct
12 Incorrect 222 ms 11860 KB Output isn't correct
13 Incorrect 202 ms 11304 KB Output isn't correct
14 Correct 245 ms 12028 KB Output is correct
15 Correct 327 ms 14756 KB Output is correct
16 Correct 379 ms 17104 KB Output is correct
17 Correct 281 ms 14624 KB Output is correct
18 Correct 284 ms 14532 KB Output is correct
19 Correct 296 ms 14540 KB Output is correct
20 Correct 298 ms 14520 KB Output is correct