Submission #676162

#	Time	Username	Problem	Language	Result	Execution time	Memory
676162		alexdd	Zoltan (COCI16_zoltan)	C++17	126 / 140	475 ms	29120 KiB

zoltan

#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll 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]];
}
ll put(ll x, ll 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;
}
pair<int,int> aint[810000];
pair<int,int> combine(pair<int,int> x, pair<int,int> y)
{
    pair<int,int> aux;
    aux.first = max(x.first, y.first);
    int auxx=0;
    if(aux.first == x.first)
        auxx += x.second;
    auxx%=MOD;
    if(aux.first == y.first)
        auxx += y.second;
    auxx%=MOD;
    aux.second = auxx;
    return aux;
}
void reset_aint()
{
    for(int i=0;i<810000;i++)
        aint[i]={0,0};
}
void upd(int nod, int st, int dr, int poz, pair<int,int> newval)
{
    if(st==dr)
    {
        aint[nod]=combine(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]);
}
pair<int,int> qry(int nod, int st, int dr, int le, int ri)
{
    if(le>ri)
        return {0,0};
    if(le==st && dr==ri)
        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));
}
pair<int,int> dp1[200001];
pair<int,int> dp2[200001];
void calc_dp1()
{
    reset_aint();
    for(int i=1;i<=cntn;i++)
        dp1[i]=dp2[i]={0,0};
    pair<int,int> x;
    for(int i=n;i>0;i--)
    {
        x = qry(1,1,cntn,a[i]+1,cntn);
        x.first = x.first + 1;
        if(x.first == 1)
            x.second = 1;
        upd(1,1,cntn,a[i],x);
        dp1[a[i]] = combine(dp1[a[i]], x);
    }
}
void calc_dp2()
{
    reset_aint();
    pair<int,int> x;
    for(int i=n;i>0;i--)
    {
        x = qry(1,1,cntn,1,a[i]-1);
        x.first = x.first + 1;
        if(x.first == 1)
            x.second = 1;
        upd(1,1,cntn,a[i],x);
        dp2[a[i]] = combine(dp2[a[i]], x);
    }
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    normalizare();
    calc_dp1();
    calc_dp2();
    pair<int,int> rez = {0,0};
    pair<int,int> x ;

    for(int i=1;i<=cntn;i++)
    {
        //cout<<i<<" "<<dp1[i].first<<" "<<dp2[i].first<<"\n";
        x.first = dp1[i].first + dp2[i].first - 1;
        x.second = (1LL*dp1[i].second * dp2[i].second)%MOD;
        rez = combine(rez, x);
    }
    if(rez.first == 1)
    {
        cout<<1<<" ";
        cout<<(put(2,n-1) * n) % MOD;
        return 0;
    }
    cout<<rez.first<<" "<<(rez.second * put(2, n-rez.first))%MOD;
    //cout<<rez.first<<" "<<rez.second;
    return 0;
}
/**


input:
20
13 6 5 15 19 18 9 4 14 17 7 10 3 1 2 8 20 16 11 12
13 6 5            4            3 1 2 8       11 12

correct output:
9 32768


*/

• Subtask 1: 126 / 140