Submission #1276831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276831		flaming_top1	Zoltan (COCI16_zoltan)	C++20	140 / 140	187 ms	18316 KiB

zoltan

#include <bits/stdc++.h>

#define SPED                                                                                                           \
    ios_base::sync_with_stdio(false);                                                                                  \
    cin.tie(0);                                                                                                        \
    cout.tie(0);
#define endl "\n"
#define fi first
#define se second
#define lint long long
#define fami signed
#define lore main
#define freefire freopen

const lint INF = 0x1f1f1f1f1f1f1f1f;
const lint NEG = 0xE1E1E1E1E1E1E1E1;
const lint mod = 1e9 + 7;

using namespace std;

int n, K;
lint a[200005];
lint maxi = -1, cnt;

lint binpow(lint x, lint k)
{
    x %= mod;
    lint r = 1 % mod;

    while (k)
    {
        if (k & 1)
            r = r * x % mod;

        x = x * x % mod;
        k >>= 1;
    }

    return r;
}

struct Seg
{
    pair<lint, lint> seg[800015];

    inline pair<lint, lint> combine(pair<lint, lint> L, pair<lint, lint> R)
    {
        if (L.fi < 0)
            return R;

        if (R.fi < 0)
            return L;

        if (L.fi != R.fi)
            return (L.fi > R.fi ? L : R);

        return {L.fi, (L.se + R.se) % mod};
    }

    void update(int node, int l, int r, int idx, pair<lint, lint> k)
    {
        if (l == r)
        {
            seg[node] = combine(seg[node], k);
            return;
        }

        int mid = (l + r) >> 1;

        if (idx <= mid)
            update(node << 1, l, mid, idx, k);
        else
            update(node << 1 | 1, mid + 1, r, idx, k);

        seg[node] = combine(seg[node << 1], seg[node << 1 | 1]);
    }

    pair<lint, lint> get(int node, int l, int r, int templ, int tempr)
    {

        if (templ <= l and r <= tempr)
            return seg[node];

        if (r < templ or tempr < l)
            return {-1, 0}; // -∞

        int mid = (l + r) >> 1;

        return combine(get(node << 1, l, mid, templ, tempr), get(node << 1 | 1, mid + 1, r, templ, tempr));
    }
} st1, st2;

void compress()
{
    vector<lint> zip(a + 1, a + 1 + n);
    sort(zip.begin(), zip.end());
    zip.erase(unique(zip.begin(), zip.end()), zip.end());
    K = (int)zip.size();

    for (int i = 1; i <= n; ++i)
        a[i] = lower_bound(zip.begin(), zip.end(), a[i]) - zip.begin() + 2;
}

fami lore()
{
    SPED;
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    compress();

    for (int i = n; i >= 1; i--)
    {

        auto lis = st1.get(1, 1, 200003, a[i] + 1, 200003);

        if (lis.fi == 0 and lis.se == 0)
            lis = {0, 1};

        auto lds = st2.get(1, 1, 200003, 1, a[i] - 1);

        if (lds.fi == 0 and lds.se == 0)
            lds = {0, 1};

        lint len = lis.fi + lds.fi + 1;

        lint ways = (lis.se * lds.se) % mod;

        if (len > maxi)
        {
            maxi = len;
            cnt = ways;
        }
        else if (len == maxi)
        {
            cnt += ways;
            cnt %= mod;
        }

        st1.update(1, 1, 200003, a[i], {lis.fi + 1, lis.se});
        st2.update(1, 1, 200003, a[i], {lds.fi + 1, lds.se});
    }

    cnt = cnt % mod * binpow(2, n - maxi) % mod;
    cout << maxi << " " << cnt << endl;
}

• Subtask 1: 140 / 140