oj.uz

Submission #681673

# Submission time Handle Problem Language Result Execution time Memory
681673 2023-01-13T16:26:14 Z finn__ Zoltan (COCI16_zoltan) C++17
7 / 140
 486 ms 30704 KB 
#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000007

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]] + 1, z.size());
        auto b = t2.range_max(0, c[y[i]] - 1);
        size_t r = a.first + b.first + 1;

        size_t h = t1.range_max(c[y[i]], c[y[i]]).second;

        if (r > ans.first)
            ans = {r, (a.second * b.second * t1.range_max(c[y[i]], c[y[i]]).second) % MOD};
        else if (r == ans.first)
            ans.second = (ans.second + a.second * b.second * t1.range_max(c[y[i]], c[y[i]]).second) % MOD;
    }

    if (ans.second & 1)
        ans.second--;

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

Compilation message

zoltan.cpp: In function 'int main()':
zoltan.cpp:105:16: warning: unused variable 'h' [-Wunused-variable]
  105 |         size_t h = t1.range_max(c[y[i]], c[y[i]]).second;
      |                ^

Subtask #1
7.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 212 KB Output isn't correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Correct 1 ms 296 KB Output is correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Incorrect 2 ms 340 KB Output isn't correct
8 Incorrect 2 ms 340 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 Incorrect 256 ms 26644 KB Output isn't correct
12 Incorrect 214 ms 25508 KB Output isn't correct
13 Incorrect 207 ms 16936 KB Output isn't correct
14 Incorrect 302 ms 25884 KB Output isn't correct
15 Incorrect 440 ms 27900 KB Output isn't correct
16 Incorrect 486 ms 30704 KB Output isn't correct
17 Incorrect 292 ms 27608 KB Output isn't correct
18 Incorrect 260 ms 27688 KB Output isn't correct
19 Incorrect 300 ms 27708 KB Output isn't correct
20 Incorrect 260 ms 27652 KB Output isn't correct