Submission #473630

#	Time	Username	Problem	Language	Result	Execution time	Memory
473630		OttoTheDino	Fish (IOI08_fish)	C++17	17 / 100	253 ms	31728 KiB

fish

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

#define rep(i,s,e)                  for (ll i = s; i <= e; ++i)
#define pb                          push_back
#define fi                          first
#define se                          second
#define all(a)                      a.begin(), a.end()
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;

const ll mx = 5e5+5;

set<ll> st;
ll nums[mx] = {}, m;

long long bin_exp (long long a, long long x) {
    long long res = 1;
    while (x>0) {
        if (x%2) res = res*a%m;
        a = a*a%m;
        x /= 2;
    }
    return res;
}

ll add_cnt (ll cnt) {
    if (cnt && --nums[cnt]==0) st.erase(cnt);
    if (++nums[++cnt]==1) st.insert(cnt);
    return cnt;
}

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

    ll f, k, ans = 0; cin >> f >> k >> m;
    vii bois;
    rep (i,0,f-1) {
        ll l, tp; cin >> l >> tp;
        bois.pb({l, tp});
    }
    sort(all(bois));
    ll last[mx], id = 0, org_cnt[mx] = {}, cnt[mx] = {}, init = 1;
    rep (i,0,f-1) last[bois[i].se] = i;
    while (bois.back().fi >= 2*bois[id].fi) {
        org_cnt[bois[id].se]=add_cnt(org_cnt[bois[id].se]);
        id++;
    }
    
    org_cnt[bois.back().se]=add_cnt(org_cnt[bois.back().se]);

    for (ll el : st) init = init*bin_exp(el+1,nums[el])%m;

    st.clear();
    memset(nums, 0, 8*mx);
    id = 0;

    rep (i,0,f-1) {
        if (i==last[bois[i].se]) {
            while (bois[i].fi >= 2*bois[id].fi) {
                cnt[bois[id].se]=add_cnt(cnt[bois[id].se]);
                id++;
            }
            if (cnt[bois[i].se]==org_cnt[bois[i].se]) {
                ll res = 1;
                for (ll el : st) {
                    if (el==cnt[bois[i].se]) {
                        if (nums[el]==1) continue; 
                        res = res*bin_exp(el+1,nums[el]-1)%m;
                    }
                    else res = res*bin_exp(el+1,nums[el])%m;
                }
                ans = (ans+res)%m;
            }
        }
    }

    cout << (init+ans+m-1)%m  << "\n";

    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 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: 5 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5