Submission #681679

#	Time	Username	Problem	Language	Result	Execution time	Memory
681679		finn__	Zoltan (COCI16_zoltan)	C++17	28 / 140	497 ms	29616 KiB

zoltan

#include <bits/stdc++.h>
using namespace std;

#define MOD (1000000007 << 1)

struct segtree
{
    vector<pair<unsigned, uint64_t>> t;
    size_t l;

    segtree(size_t n)
    {
        l = 1 << (32 - __builtin_clz(n));
        t = vector<pair<unsigned, uint64_t>>(2 * l, {0, 1});
    }

    pair<unsigned, uint64_t> merge(
        pair<unsigned, uint64_t> const &a, pair<unsigned, uint64_t> const &b)
    {
        if (!a.first && !b.first)
            return {0, 1};
        if (a.first == b.first)
            return make_pair(a.first, (a.second + b.second) % MOD);
        return max(a, b);
    }

    void update(size_t i, pair<unsigned, uint64_t> x)
    {
        i += l;
        if (t[i].first < x.first)
            t[i] = x;
        else if (t[i].first == x.first)
            t[i].second = (t[i].second + x.second) % MOD;
        else
            return;

        while (i > 1)
        {
            i >>= 1;
            t[i] = merge(t[2 * i], t[2 * i + 1]);
        }
    }

    pair<unsigned, uint64_t> range_max(size_t i, size_t j)
    {
        i += l, j += l;
        pair<unsigned, uint64_t> x = {0, 0};

        while (i <= j)
        {
            if (i & 1)
                x = merge(x, t[i++]);
            if (!(j & 1))
                x = merge(t[j--], x);

            i >>= 1;
            j >>= 1;
        }

        return x;
    }
};

int main()
{
    size_t n;
    cin >> n;

    vector<uint64_t> pow2(n + 1);
    pow2[0] = 1;
    for (size_t i = 1; i <= n; i++)
        pow2[i] = (pow2[i - 1] << 1) % MOD;

    vector<unsigned> y(n), z;
    for (unsigned &x : y)
    {
        cin >> x;
        z.push_back(x);
    }
    z.push_back(0);
    sort(z.begin(), z.end());
    z.resize(unique(z.begin(), z.end()) - z.begin());
    unordered_map<unsigned, unsigned> c;
    for (size_t i = 0; i < z.size(); i++)
        c[z[i]] = i;

    segtree t1(z.size() + 1), t2(z.size() + 1);

    for (size_t i = n - 1; i < n; i--)
    {
        pair<unsigned, uint64_t> x = t1.range_max(c[y[i]] + 1, z.size());
        t1.update(c[y[i]], {x.first + 1, x.second});

        x = t2.range_max(0, c[y[i]] - 1);
        t2.update(c[y[i]], {x.first + 1, x.second});
    }

    pair<unsigned, uint64_t> ans = {0, 0};
    for (size_t i = 0; i < n; i++)
    {
        auto a = t1.range_max(c[y[i]], z.size());
        auto b = t2.range_max(0, c[y[i]] - 1);
        size_t r = a.first + b.first;

        if (r > ans.first)
            ans = {r, (a.second * b.second) % MOD};
        else if (r == ans.first)
            ans.second = (ans.second + a.second * b.second) % MOD;
    }

    size_t p = 1;
    if (!(ans.second & 1))
    {
        ans.second >>= 1;
        p = 0;
    }

    cout << ans.first << ' ' << (ans.second * pow2[n - ans.first - p]) % (MOD >> 1) << '\n';
}

• Subtask 1: 28 / 140