제출 #1269227

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269227		DangKhoizzzz	Zoltan (COCI16_zoltan)	C++20	140 / 140	289 ms	20116 KiB

zoltan

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

using namespace std;

const int INF = 1e18;
const int maxn = 2e5 + 7;
const int mod = 1e9 + 7;

pii merging(pii a, pii b)
{
    if(a.fi == b.fi) return {a.fi, (a.se + b.se)%mod};
    else return max(a, b);
}

struct Segment_Tree
{
    pii st[maxn*4];
    void update(int id, int l, int r, int pos, pii val)
    {
        if(r < pos || l > pos) return;
        if(l == r)
        {
            st[id] = merging(val , st[id]);
            st[id].se %= mod;
            return;
        }
        int mid = (l+r) >> 1;
        update(id*2, l, mid, pos, val);
        update(id*2+1, mid+1, r, pos, val);
        st[id] = merging(st[id*2], st[id*2+1]);
        st[id].se %= mod;
    }
    pii get(int id, int l, int r, int u, int v)
    {
        if(r < u || l > v) return {-INF, 0};
        if(u <= l && r <= v) return st[id];
        int mid = (l+r) >> 1;
        return merging(get(id*2, l, mid, u, v), get(id*2+1, mid+1, r, u, v));
    }
} ST[2];

int n , a[maxn] , pow2[maxn];
pii ans = {0 , 0};

void compress()
{
    vector <int> val;
    for(int i = 1; i <= n; i++) val.push_back(a[i]);
    sort(val.begin(), val.end());
    val.erase(unique(val.begin(), val.end()), val.end());
    for(int i = 1; i <= n; i++) a[i] = upper_bound(val.begin(), val.end(), a[i]) - val.begin();
}

void solve()
{
    pow2[0] = 1;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        pow2[i] = (pow2[i-1]*2)%mod;
    }
    compress();

    ST[1].update(1 , 0 , n+1 , n+1 , (pii){0 , 1});
    for(int i = n; i >= 2; i--)
    {
        pii upd = ST[1].get(1 , 0 , n+1 , a[i] + 1 , n+1); upd.fi++;
        ST[1].update(1 , 0 , n+1 , a[i] , upd);
    }

    ST[0].update(1 , 0 , n+1 , 0 , (pii){0 , 1});
    for(int i = n; i >= 2; i--)
    {
        pii upd = ST[0].get(1 , 0 , n+1 , 0 , a[i] - 1); upd.fi++;
        ST[0].update(1 , 0 , n+1 , a[i] , upd);
    }

    pii temp1 = ST[0].get(1 , 0 , n+1 , 0 , a[1] - 1);
    pii temp2 = ST[1].get(1 , 0 , n+1 , a[1]+1 , n+1);

    ans.fi = temp1.fi + temp2.fi + 1;
    ans.se = (((temp1.se * temp2.se)%mod) * pow2[n - ans.fi])%mod;

    for(int i = 0; i <= n; i++)
    {
        pii tmp1 = ST[0].get(1 , 0 , n+1 , i , i);
        pii tmp2 = ST[1].get(1 , 0 , n+1 , i+1 , n+1);

        pii res;

        res.fi = tmp1.fi + tmp2.fi;
        res.se = (((tmp1.se*tmp2.se)%mod)*pow2[n - 1 - res.fi])%mod;
        ans = merging(res , ans);
    }
    cout << ans.fi << ' ' << ans.se << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

• Subtask 1: 140 / 140