oj.uz

Submission #676160

# Submission time Handle Problem Language Result Execution time Memory
676160 2022-12-29T15:16:09 Z alexdd Zoltan (COCI16_zoltan) C++17
119 / 140
 545 ms 29156 KB 
#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);
    }
    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
119.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6624 KB Output is correct
2 Correct 4 ms 6664 KB Output is correct
3 Correct 3 ms 6612 KB Output is correct
4 Correct 5 ms 6612 KB Output is correct
5 Correct 3 ms 6612 KB Output is correct
6 Incorrect 3 ms 6612 KB Output isn't correct
7 Correct 5 ms 6740 KB Output is correct
8 Correct 5 ms 6740 KB Output is correct
9 Correct 5 ms 6740 KB Output is correct
10 Correct 5 ms 6708 KB Output is correct
11 Correct 318 ms 24668 KB Output is correct
12 Correct 254 ms 22092 KB Output is correct
13 Correct 241 ms 21300 KB Output is correct
14 Correct 369 ms 22216 KB Output is correct
15 Correct 435 ms 26060 KB Output is correct
16 Correct 545 ms 29156 KB Output is correct
17 Correct 366 ms 25756 KB Output is correct
18 Incorrect 338 ms 25736 KB Output isn't correct
19 Correct 355 ms 25804 KB Output is correct
20 Incorrect 377 ms 25636 KB Output isn't correct