제출 #676066

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
676066		alexdd	Zoltan (COCI16_zoltan)	C++17	0 / 140	638 ms	45024 KiB

zoltan

#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1000000007;
int n;
int a[200001];
map<int,int> mp;
map<int,int> nor;
int cntn=0;
void normalizare()
{
    for(int i=1;i<=n;i++)
        mp[a[i]]++;
    int val;
    for(auto it:mp)
    {
        val=it.first;
        cntn++;
        nor[val]=cntn;
    }
    for(int i=1;i<=n;i++)
        a[i]=nor[a[i]];
}
struct node
{
    int mxm[2];
    int cnt[2];
};
node combine(node x, node y)
{
    node rez;
    for(int i=0;i<2;i++)
    {
        rez.mxm[i] = max(x.mxm[i],y.mxm[i]);
        rez.cnt[i] = 0;
        if(x.mxm[i]==rez.mxm[i])
            rez.cnt[i] += x.cnt[i];
        if(y.mxm[i]==rez.mxm[i])
            rez.cnt[i] += y.cnt[i];
    }
    rez.cnt[0]%=MOD;
    rez.cnt[1]%=MOD;
    return rez;
}
node aint[810000];
node gol;
void upd(int nod, int st, int dr, int poz, node newval)
{
    if(st==dr)
    {
        aint[nod]=newval;
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij)
        upd(nod*2,st,mij,poz,newval);
    else
        upd(nod*2+1,mij+1,dr,poz,newval);
    aint[nod]=combine(aint[nod*2],aint[nod*2+1]);
}
node qry(int nod, int st, int dr, int le, int ri)
{
    if(le>ri)
        return gol;
    if(le==st && ri==dr)
        return aint[nod];
    int mij=(st+dr)/2;
    return combine(qry(nod*2,st,mij,le,min(mij,ri)),
                   qry(nod*2+1,mij+1,dr,max(mij+1,le),ri));
}
int put(int x, int exp)
{
    if(exp==0) return 1;
    if(exp%2==0) return put((x*x)%MOD, exp/2);
    else return (put((x*x)%MOD, exp/2)*x)%MOD;
}
signed main()
{
    gol.mxm[0]=0;
    gol.mxm[1]=0;
    gol.cnt[0]=0;
    gol.cnt[1]=0;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    normalizare();
    node dp;
    node x;
    for(int i=1;i<=n;i++)
    {
        x = qry(1,1,cntn,a[i]+1,cntn);
        dp.mxm[0] = x.mxm[0] + 1;
        dp.cnt[0] = x.cnt[0];
        if(dp.mxm[0]==1)
            dp.cnt[0]=1;

        x = qry(1,1,cntn,1,a[i]-1);
        dp.mxm[1] = max(x.mxm[0], x.mxm[1]) + 1;
        dp.cnt[1]=0;
        if(x.mxm[0] + 1 == dp.mxm[1])
            dp.cnt[1] += x.cnt[0];
        if(x.mxm[1] + 1 == dp.mxm[1])
            dp.cnt[1] += x.cnt[1];

        if(dp.mxm[1]==1)
            dp.cnt[1]=1;
        dp.cnt[1]%=MOD;
        dp.cnt[0]%=MOD;

        upd(1,1,cntn,a[i],dp);
    }
    x = aint[1];
    int maxim=0,cntm=0;
    maxim=max(x.mxm[0],x.mxm[1]);
    if(x.mxm[0]==maxim)
        cntm+=x.cnt[0];
    if(x.mxm[1]==maxim)
        cntm+=x.cnt[1];
    cout<<maxim<<" "<<(cntm*put(2,n-maxim))%MOD;
    return 0;
}
/**

trebuie sa gasesc 2 secvente, una fiind crescatoare si cealalta descrescatoare
cea crescatoare incepe unde se termina cea descrescatoare

dp[i][0] = lungimea maxima a unei secvente descrescatoare care se termina pe pozitia i
dp[i][1] = lungimea maxima a 2 secvente, prima descrescatoare, a 2-a crescatoare, care se termina pe pozitia i

dp[i][0] = max(dp[j][0] + 1), unde a[j] > a[i]
dp[i][1] = max(max(dp[j][1] + 1 cu a[j] < a[i]), max(dp[j][0] + 1 cu a[j] < a[i]))

*/

• Subtask 1: 0 / 140