oj.uz

Submission #676158

# Submission time Handle Problem Language Result Execution time Memory
676158 2022-12-29T15:12:36 Z alexdd Zoltan (COCI16_zoltan) C++17
14 / 140
 560 ms 47508 KB 
#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
const int 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;
    if(aux.first == y.first)
        auxx += y.second;
    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 = dp1[i].second * dp2[i].second;
        rez = combine(rez, x);
    }
    //cout<<rez.first<<" "<<rez.second * put(2, n-rez.first);
    cout<<rez.first<<" "<<rez.second;
    return 0;
}
/**



*/

Subtask #1
14.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 13012 KB Output isn't correct
2 Incorrect 7 ms 13012 KB Output isn't correct
3 Incorrect 6 ms 13008 KB Output isn't correct
4 Correct 7 ms 12884 KB Output is correct
5 Correct 6 ms 12884 KB Output is correct
6 Incorrect 6 ms 13012 KB Output isn't correct
7 Incorrect 9 ms 13124 KB Output isn't correct
8 Incorrect 11 ms 13140 KB Output isn't correct
9 Incorrect 8 ms 13120 KB Output isn't correct
10 Incorrect 10 ms 13120 KB Output isn't correct
11 Runtime error 311 ms 40220 KB Memory limit exceeded
12 Runtime error 232 ms 36556 KB Memory limit exceeded
13 Runtime error 242 ms 35216 KB Memory limit exceeded
14 Runtime error 352 ms 36960 KB Memory limit exceeded
15 Runtime error 499 ms 42796 KB Memory limit exceeded
16 Runtime error 560 ms 47508 KB Memory limit exceeded
17 Runtime error 335 ms 41924 KB Memory limit exceeded
18 Runtime error 340 ms 42004 KB Memory limit exceeded
19 Runtime error 355 ms 41992 KB Memory limit exceeded
20 Runtime error 333 ms 42148 KB Memory limit exceeded