oj.uz

답안 #504097

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
504097 2022-01-09T18:19:40 Z Deepesson Zoltan (COCI16_zoltan) C++17
140 / 140
 383 ms 17004 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;

///The first number is the size of the sequence, and the second one the number of sequences
pii comb(pii a,pii b){
    if(a.first==b.first){
        ///I'm multiplying MOD by two because I will divide by two later
        a.second%=(MOD*2);
        b.second%=(MOD*2);
        return {a.first,a.second+b.second%(MOD*2)};
    }else return std::max(a,b);
}

///Basic seg3

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]);
}

///Binary exponentiation + Mod

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()
{
    ///You can always start an empty subsequence
    pii base = {0,1};
    int N;
    std::cin>>N;
    int array[N]={};
    for(auto&x:array)std::cin>>x;
    int curbesto=0;
    ///Coordinate Compression
    {
        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;
    }
    ///Longest decreasing subsequence (From end to start)
    ///Notice that if you reverse this sequence it's increasing
    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);
    }
    ///Longest increasing subsequence (From end to start)
    ///Notice that if you reverse this sequence it's decreasing
    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);
    }
    ///The idea is the following:
    ///You want the largest increasing subsequence smaller than X (you will throw everything to the left)
    ///And the largest decreasing subsequence greater or equal than X(You will throw to the right)
    ///The other N-(LIS.size) don't really matter, you can throw whenever you want.
    ///That's why we will use binary exponentiation

    pii best={1,N};
    for(int i=4;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);
    }

    ///The first element can't be thrown to the right nor left: It needs to be in the middle
    ///That's why we are dividing by two :)
    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
140.0 / 140.0

# 결과 실행 시간 메모리 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 0 ms 332 KB Output is 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 460 KB Output is correct
11 Correct 246 ms 13616 KB Output is correct
12 Correct 204 ms 11856 KB Output is correct
13 Correct 193 ms 11296 KB Output is correct
14 Correct 248 ms 11948 KB Output is correct
15 Correct 342 ms 14840 KB Output is correct
16 Correct 383 ms 17004 KB Output is correct
17 Correct 293 ms 14516 KB Output is correct
18 Correct 287 ms 14556 KB Output is correct
19 Correct 312 ms 14540 KB Output is correct
20 Correct 286 ms 14536 KB Output is correct