Submission #1344920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1344920		paulica	Fish (IOI08_fish)	C++20	0 / 100	199 ms	8376 KiB

fish

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

typedef long long ll;
typedef long double ld;

//const int MOD = 998244353;

/*
ll pwr(ll a, ll b) {
    if (b < 0) b += MOD - 1;
    ll res = 1;
    for (; b; b /= 2) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
    }
    return res;
}
*/

const int MAXN = 2e5 + 10;
const int INF = 1e9;

int MOD;

const int OFF = 1 << 20;

struct SegTree {
    ll tree[2 * OFF];

    void update(int i, int val) {
        i += OFF;
        tree[i] = val;
        for (i /= 2; i; i /= 2)
            tree[i] = tree[2 * i] * tree[2 * i + 1] % MOD;
    }

    ll query(int l, int r, int i = 1, int lo = 0, int hi = OFF) {
        if (l <= lo && hi <= r) return tree[i];
        if (r <= lo || hi <= l) return 1;
        int mid = (lo + hi) / 2;
        return
            query(l, r, 2 * i + 0, lo, mid) *
            query(l, r, 2 * i + 1, mid, hi) % MOD;
    }
    
} T;

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

    int F, K;
    cin >> F >> K >> MOD;
    vector<pair<int, int>> fish(F);
    for (auto& [len, gem] : fish) {
        cin >> len >> gem;
    }

    vector<int> gem_cnt(K + 1, 0);
    for (auto& [len, gem] : fish) gem_cnt[gem]++;
    for (int i = 1; i <= K; i++) T.update(i, gem_cnt[i] + 1);

    sort(fish.rbegin(), fish.rend());

    int biggest_in = 0;
    vector<bool> is_active(K + 1, true);

    ll sol = 0;

    for (auto& [len, gem] : fish) {
        while (biggest_in < F) {
            auto& [len_in, gem_in] = fish[biggest_in];
            if (len_in * 2 > len) {
                if (is_active[gem_in]) {
                    gem_cnt[gem_in]--;
                    T.update(gem_in, gem_cnt[gem_in] + 1);
                } else assert(gem_cnt[gem_in] == 0);
                biggest_in++;
            } else break;
        }

        assert(gem_cnt[gem] >= 0);
        if (!is_active[gem]) continue;

        sol += T.query(1, K + 1);

        gem_cnt[gem] = 0;
        T.update(gem, 1);
        is_active[gem] = false;
    }

    sol %= MOD;

    cout << sol << '\n';

    return 0;
}

• 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