Submission #1338636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1338636		po_rag526	Zoltan (COCI16_zoltan)	C++17	140 / 140	250 ms	31484 KiB

zoltan

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MOD = 1e9 + 7;

long long power(long long base, long long exp)
{
    long long res = 1;
    base %= MOD;
    while (exp > 0)
    {
        if (exp % 2 == 1)
            res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

struct Node
{
    int max_len;
    long long count;
    Node() : max_len(0), count(0) {}
    Node(int l, long long c) : max_len(l), count(c) {}
};

Node combine(const Node &a, const Node &b)
{
    if (a.max_len > b.max_len)
        return a;
    if (b.max_len > a.max_len)
        return b;
    return Node(a.max_len, (a.count + b.count) % MOD);
}

class SegTree
{
    int n;
    vector<Node> tree;

    void update(int node, int start, int end, int idx, int val_len, long long val_cnt)
    {
        if (start == end)
        {
            if (val_len > tree[node].max_len)
            {
                tree[node].max_len = val_len;
                tree[node].count = val_cnt;
            }
            else if (val_len == tree[node].max_len)
            {
                tree[node].count = (tree[node].count + val_cnt) % MOD;
            }
            return;
        }
        int mid = start + (end - start) / 2;
        if (idx <= mid)
        {
            update(2 * node, start, mid, idx, val_len, val_cnt);
        }
        else
        {
            update(2 * node + 1, mid + 1, end, idx, val_len, val_cnt);
        }
        tree[node] = combine(tree[2 * node], tree[2 * node + 1]);
    }

    Node query(int node, int start, int end, int l, int r)
    {
        if (r < start || end < l || l > r)
            return Node(0, 0);
        if (l <= start && end <= r)
            return tree[node];
        int mid = start + (end - start) / 2;
        return combine(query(2 * node, start, mid, l, r),
                       query(2 * node + 1, mid + 1, end, l, r));
    }

public:
    SegTree(int n) : n(n), tree(4 * n) {}

    void update(int idx, int val_len, long long val_cnt)
    {
        update(1, 0, n - 1, idx, val_len, val_cnt);
    }

    Node query(int l, int r)
    {
        if (l > r)
            return Node(0, 0);
        return query(1, 0, n - 1, l, r);
    }
};

void solve()
{
    int n;
    if (!(cin >> n))
        return;

    vector<int> a(n);
    vector<int> coords(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        coords[i] = a[i];
    }

    sort(coords.begin(), coords.end());
    coords.erase(unique(coords.begin(), coords.end()), coords.end());
    int M = coords.size();

    auto get_id = [&](int x)
    {
        return lower_bound(coords.begin(), coords.end(), x) - coords.begin();
    };

    SegTree st_inc(M), st_dec(M);

    vector<int> inc_len(n), dec_len(n);
    vector<long long> inc_cnt(n), dec_cnt(n);

    for (int i = n - 1; i >= 0; i--)
    {
        int val_idx = get_id(a[i]);

        Node res_inc = st_inc.query(val_idx + 1, M - 1);
        if (res_inc.max_len == 0)
        {
            inc_len[i] = 1;
            inc_cnt[i] = 1;
        }
        else
        {
            inc_len[i] = res_inc.max_len + 1;
            inc_cnt[i] = res_inc.count;
        }
        st_inc.update(val_idx, inc_len[i], inc_cnt[i]);

        Node res_dec = st_dec.query(0, val_idx - 1);
        if (res_dec.max_len == 0)
        {
            dec_len[i] = 1;
            dec_cnt[i] = 1;
        }
        else
        {
            dec_len[i] = res_dec.max_len + 1;
            dec_cnt[i] = res_dec.count;
        }
        st_dec.update(val_idx, dec_len[i], dec_cnt[i]);
    }

    int optimal_len = 0;
    for (int i = 0; i < n; i++)
    {
        optimal_len = max(optimal_len, inc_len[i] + dec_len[i] - 1);
    }
    long long total_count = 0;
    for (int i = 0; i < n; i++)
    {
        if (inc_len[i] + dec_len[i] - 1 == optimal_len)
        {
            long long ways = (inc_cnt[i] * dec_cnt[i]) % MOD;
            long long multipliers = power(2, n - optimal_len);
            ways = (ways * multipliers) % MOD;
            total_count = (total_count + ways) % MOD;
        }
    }
    cout << optimal_len << " " << total_count << "\n";
}

int main()
{

    int t = 1;
    while (t--)
    {
        solve();
    }

    return 0;
}

• Subtask 1: 140 / 140