oj.uz

Submission #676165

# Submission time Handle Problem Language Result Execution time Memory
676165 2022-12-29T15:31:30 Z alexdd Zoltan (COCI16_zoltan) C++17
140 / 140
 507 ms 29048 KB 
#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
ifstream fin("citire.in");
#define ll long long
//#define cin fin
const ll MOD = 1000000007;
int n;
int a[200005];
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[200005];
pair<int,int> dp2[200005];
void calc_dp1()
{
    reset_aint();
    for(int i=1;i<=n;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);
        dp1[i] = combine(dp1[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);
        dp2[i] = combine(dp2[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++)
    {
        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;
    return 0;
}
/**

correct output:
80006 428693327



*/

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 3 ms 6612 KB Output is correct
3 Correct 3 ms 6612 KB Output is correct
4 Correct 3 ms 6612 KB Output is correct
5 Correct 3 ms 6612 KB Output is correct
6 Correct 3 ms 6612 KB Output is correct
7 Correct 4 ms 6740 KB Output is correct
8 Correct 5 ms 6740 KB Output is correct
9 Correct 5 ms 6764 KB Output is correct
10 Correct 4 ms 6740 KB Output is correct
11 Correct 319 ms 24564 KB Output is correct
12 Correct 243 ms 22104 KB Output is correct
13 Correct 229 ms 21208 KB Output is correct
14 Correct 364 ms 22152 KB Output is correct
15 Correct 385 ms 26172 KB Output is correct
16 Correct 507 ms 29048 KB Output is correct
17 Correct 363 ms 26252 KB Output is correct
18 Correct 343 ms 26232 KB Output is correct
19 Correct 351 ms 26252 KB Output is correct
20 Correct 328 ms 26244 KB Output is correct