oj.uz

Submission #676166

# Submission time Handle Problem Language Result Execution time Memory
676166 2022-12-29T15:33:50 Z alexdd Zoltan (COCI16_zoltan) C++17
140 / 140
 467 ms 29148 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<=n;i++)
    {
        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;
    return 0;
}
/**

correct output:
80006 428693327



*/

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6624 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 5 ms 6740 KB Output is correct
8 Correct 4 ms 6740 KB Output is correct
9 Correct 6 ms 6772 KB Output is correct
10 Correct 5 ms 6740 KB Output is correct
11 Correct 292 ms 24692 KB Output is correct
12 Correct 240 ms 22104 KB Output is correct
13 Correct 236 ms 21232 KB Output is correct
14 Correct 304 ms 22224 KB Output is correct
15 Correct 438 ms 25976 KB Output is correct
16 Correct 467 ms 29148 KB Output is correct
17 Correct 354 ms 26256 KB Output is correct
18 Correct 329 ms 26232 KB Output is correct
19 Correct 351 ms 26256 KB Output is correct
20 Correct 331 ms 26320 KB Output is correct