oj.uz

Submission #687714

# Submission time Handle Problem Language Result Execution time Memory
687714 2023-01-26T21:40:28 Z finn__ Fish (IOI08_fish) C++17
0 / 100
 270 ms 9428 KB 
#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)
    {
        if (j > l)
            return 1;
        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--;

        types[g].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());
    vector<unsigned> finv(k);
    for (size_t i = 0; i < k; i++)
        finv[types[i].g] = i;
    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(finv[fish[j].second]);
            j++;
        }

        auto const &[g, l1, l2] = types[i];
        ans = (ans + ((tree.range_prod(0, i - 1) * (tree.range_prod(i, i) - 1 + m)) % m)) % 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)) % m;
    }

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

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 1876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 93 ms 2676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 166 ms 4180 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 2708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 149 ms 4160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 183 ms 4696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 154 ms 4672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 224 ms 8156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 174 ms 8168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 270 ms 9428 KB Output isn't correct
2 Halted 0 ms 0 KB -