oj.uz

Submission #504085

# Submission time Handle Problem Language Result Execution time Memory
504085 2022-01-09T17:51:35 Z Deepesson Zoltan (COCI16_zoltan) C++17
77 / 140
 377 ms 35092 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){
        assert(a.second+b.second<MOD*MOD);
        return {a.first,a.second+b.second%MOD};
    }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;
    {
        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(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";
    std::cout<<best.first<<" "<<((((best.second/2)%MOD)*binpow(2,N-best.first,MOD))%MOD)<<"\n";
}

Subtask #1
77.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 348 KB Output is correct
2 Correct 71 ms 352 KB Output is correct
3 Correct 69 ms 332 KB Output is correct
4 Incorrect 68 ms 364 KB Output isn't correct
5 Incorrect 71 ms 364 KB Output isn't correct
6 Incorrect 74 ms 364 KB Output isn't correct
7 Correct 70 ms 476 KB Output is correct
8 Correct 70 ms 476 KB Output is correct
9 Correct 70 ms 460 KB Output is correct
10 Correct 69 ms 460 KB Output is correct
11 Incorrect 263 ms 14228 KB Output isn't correct
12 Incorrect 234 ms 12564 KB Output isn't correct
13 Incorrect 222 ms 11764 KB Output isn't correct
14 Runtime error 239 ms 24656 KB Execution killed with signal 6
15 Runtime error 305 ms 30468 KB Execution killed with signal 6
16 Runtime error 377 ms 35092 KB Execution killed with signal 6
17 Correct 323 ms 15312 KB Output is correct
18 Correct 309 ms 15048 KB Output is correct
19 Correct 320 ms 15168 KB Output is correct
20 Correct 312 ms 15160 KB Output is correct