oj.uz

Submission #676163

# Submission time Handle Problem Language Result Execution time Memory
676163 2022-12-29T15:30:16 Z alexdd Zoltan (COCI16_zoltan) C++17
0 / 140
 5 ms 6684 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);
    }
    cout<<rez.first<<" "<<(rez.second * put(2, n-rez.first))%MOD;
    return 0;
}
/**

correct output:
80006 428693327



*/

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 6612 KB Output isn't correct
2 Incorrect 4 ms 6612 KB Output isn't correct
3 Incorrect 3 ms 6612 KB Output isn't correct
4 Incorrect 5 ms 6612 KB Output isn't correct
5 Incorrect 3 ms 6612 KB Output isn't correct
6 Incorrect 3 ms 6612 KB Output isn't correct
7 Incorrect 4 ms 6612 KB Output isn't correct
8 Incorrect 4 ms 6612 KB Output isn't correct
9 Incorrect 4 ms 6684 KB Output isn't correct
10 Incorrect 3 ms 6612 KB Output isn't correct
11 Incorrect 3 ms 6612 KB Output isn't correct
12 Incorrect 3 ms 6612 KB Output isn't correct
13 Incorrect 3 ms 6612 KB Output isn't correct
14 Incorrect 4 ms 6612 KB Output isn't correct
15 Incorrect 4 ms 6612 KB Output isn't correct
16 Incorrect 3 ms 6612 KB Output isn't correct
17 Incorrect 3 ms 6612 KB Output isn't correct
18 Incorrect 5 ms 6612 KB Output isn't correct
19 Incorrect 4 ms 6612 KB Output isn't correct
20 Incorrect 3 ms 6612 KB Output isn't correct