Submission #687685

#	Time	Username	Problem	Language	Result	Execution time	Memory
687685		finn__	Fish (IOI08_fish)	C++17	0 / 100	260 ms	16588 KiB

fish

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

class SegmentTree
{
    vector<unsigned> t;
    size_t l, m;

public:
    SegmentTree(size_t _n, size_t _m)
    {
        l = 1 << (32 - __builtin_clz(_n));
        m = _m;
        t = vector<unsigned>(2 * l, 1);
    }

    void increment(size_t i)
    {
        i += l;
        t[i] = (t[i] + 1) % m;

        while (i >>= 1)
            t[i] = (t[2 * i] * t[2 * i + 1]) % m;
    }

    unsigned range_prod(size_t i, size_t j)
    {
        unsigned x = 1;
        i += l, j += l;

        while (i <= j)
        {
            if (i & 1)
                x = (x * t[i++]) % m;
            if (!(j & 1))
                x = (x * t[j--]) % m;
            i >>= 1;
            j >>= 1;
        }

        return x;
    }
};

struct JewelType
{
    unsigned g, largest = 0, second_largest = 0;

    bool operator<(JewelType const &x) const
    {
        return largest < x.largest;
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n, k, m;
    cin >> n >> k >> m;

    vector<pair<unsigned, unsigned>> fish(n);
    vector<JewelType> types(k);

    for (auto &[l, g] : fish)
    {
        cin >> l >> g;
        g--;

        if (l >= types[g].largest)
        {
            types[g].second_largest = types[g].largest;
            types[g].largest = l;
        }
        else if (l > types[g].second_largest)
            types[g].second_largest = l;
    }

    sort(fish.begin(), fish.end());
    sort(types.begin(), types.end());
    unsigned ans = 0;
    SegmentTree tree(k, m);
    size_t j = 0;

    for (size_t i = 0; i < k; i++)
    {
        while (j < n && fish[j].first <= types[i].largest)
        {
            tree.increment(fish[j].second);
            j++;
        }

        auto const &[g, l1, l2] = types[i];
        ans = (ans + tree.range_prod(0, i)) % m;
        size_t const w =
            lower_bound(types.begin(), types.end(), (JewelType){0U, 2 * l2, 0U}) - types.begin();
        if (i + 2 <= w)
            ans = (ans + tree.range_prod(i + 1, w - 1)) % m;
    }

    cout << ans << '\n';
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6
• Subtask 10: 0 / 6
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 7
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5