oj.uz

답안 #676159

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
676159 2022-12-29T15:14:32 Z alexdd Zoltan (COCI16_zoltan) C++17
63 / 140
 581 ms 45644 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;
    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 = (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
63.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 12884 KB Output is correct
2 Correct 8 ms 12884 KB Output is correct
3 Correct 7 ms 12944 KB Output is correct
4 Correct 7 ms 12884 KB Output is correct
5 Correct 7 ms 13012 KB Output is correct
6 Incorrect 7 ms 12884 KB Output isn't correct
7 Correct 7 ms 13140 KB Output is correct
8 Correct 8 ms 13140 KB Output is correct
9 Correct 8 ms 13140 KB Output is correct
10 Correct 9 ms 13080 KB Output is correct
11 Runtime error 287 ms 38988 KB Memory limit exceeded
12 Runtime error 241 ms 35504 KB Memory limit exceeded
13 Runtime error 233 ms 34160 KB Memory limit exceeded
14 Runtime error 334 ms 35608 KB Memory limit exceeded
15 Runtime error 477 ms 41104 KB Memory limit exceeded
16 Runtime error 581 ms 45644 KB Memory limit exceeded
17 Runtime error 338 ms 40780 KB Memory limit exceeded
18 Runtime error 346 ms 40696 KB Memory limit exceeded
19 Runtime error 346 ms 40704 KB Memory limit exceeded
20 Runtime error 343 ms 40604 KB Memory limit exceeded