oj.uz

Submission #681679

# Submission time Handle Problem Language Result Execution time Memory
681679 2023-01-13T16:46:18 Z finn__ Zoltan (COCI16_zoltan) C++17
28 / 140
 497 ms 29616 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Incorrect 0 ms 300 KB Output isn't correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 0 ms 304 KB Output isn't correct
7 Incorrect 2 ms 340 KB Output isn't correct
8 Incorrect 2 ms 436 KB Output isn't correct
9 Incorrect 2 ms 340 KB Output isn't correct
10 Incorrect 2 ms 340 KB Output isn't correct
11 Correct 247 ms 26268 KB Output is correct
12 Correct 209 ms 25380 KB Output is correct
13 Correct 184 ms 16712 KB Output is correct
14 Incorrect 323 ms 25356 KB Output isn't correct
15 Incorrect 427 ms 27052 KB Output isn't correct
16 Incorrect 497 ms 29616 KB Output isn't correct
17 Incorrect 254 ms 27116 KB Output isn't correct
18 Incorrect 286 ms 27284 KB Output isn't correct
19 Incorrect 267 ms 27216 KB Output isn't correct
20 Incorrect 261 ms 27324 KB Output isn't correct