Submission #1108892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108892		windowwife	Zoltan (COCI16_zoltan)	C++14	140 / 140	497 ms	17912 KiB

zoltan

#include <bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e6 + 2, mod = 1e9 + 7;
int n, a[maxn], b[maxn], id, mx = 0, cnt = 0, mx2 = 0, cnt2 = 0;
vector<int> v;
pair<int, int> res[maxn], st[4*maxn];
pair<int, int> merge (pair<int, int> a, pair<int, int> b)
{
    if (a.first == 0 && b.first == 0) return {0, 1};
    if (a < b) swap(a, b);
    if (a.first == b.first)
    {
        a.second += b.second;
        if (a.second >= mod) a.second -= mod;
    }
    return a;
}
void build (int node, int l, int r)
{
    if (l == r)
    {
        st[node] = {0, 1};
        return;
    }
    int mid = (l + r)/2;
    build(2*node, l, mid);
    build(2*node + 1, mid + 1, r);
    st[node] = merge(st[2*node], st[2*node + 1]);
}
void update (int node, int l, int r, int idx, pair<int, int> res)
{
    if (l == r)
    {
        st[node] = merge(st[node], res);
        return;
    }
    int mid = (l + r)/2;
    if (idx <= mid) update(2*node, l, mid, idx, res);
    else update(2*node + 1, mid + 1, r, idx, res);
    st[node] = merge(st[2*node], st[2*node + 1]);
}
pair<int, int> get (int node, int l, int r, int cl, int cr)
{
    if (cl > cr) return {0, 1};
    if (r < cl || cr < l) return {-1, 0};
    if (cl <= l && r <= cr) return st[node];
    int mid = (l + r)/2;
    return merge(get(2*node, l, mid, cl, cr), get(2*node + 1, mid + 1, r, cl, cr));
}
int p (int ok)
{
    ll res = 1, a = 2;
    for (; ok > 0; ok >>= 1)
    {
        if (ok & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}
int main()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        v.push_back(a[i]);
        b[n - i + 1] = b[n + i - 1] = a[i];
    }
    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());
    build(1, 1, n);
    for (int i = 1; i <= 2*n - 1; i++)
    {
        id = upper_bound(v.begin(), v.end(), b[i]) - v.begin();
        res[i] = get(1, 1, n, 1, id - 1);
        res[i].first++;
        update(1, 1, n, id, res[i]);
        if (mx < res[i].first)
        {
            mx = res[i].first;
            cnt = res[i].second;
        }
        else if (mx == res[i].first)
        {
            cnt += res[i].second;
            if (cnt >= mod) cnt -= mod;
        }
    }
    build(1, 1, n);
    for (int i = 1; i <= 2*n - 1; i++)
    {
        if (i == n) continue;
        id = upper_bound(v.begin(), v.end(), b[i]) - v.begin();
        res[i] = get(1, 1, n, 1, id - 1);
        res[i].first++;
        update(1, 1, n, id, res[i]);
        if (mx2 < res[i].first)
        {
            mx2 = res[i].first;
            cnt2 = res[i].second;
        }
        else if (mx2 == res[i].first)
        {
            cnt2 += res[i].second;
            if (cnt2 >= mod) cnt2 -= mod;
        }
    }
    if (mx > mx2) cout << mx << " " << 1LL*cnt*p(n - mx)%mod;
    else cout << mx << " " << (1LL*(cnt - cnt2)*p(n - mx)%mod + 1LL*cnt2*p(n - mx - 1)%mod)%mod;
}

• Subtask 1: 140 / 140