oj.uz

Submission #473627

# Submission time Handle Problem Language Result Execution time Memory
473627 2021-09-15T18:14:48 Z OttoTheDino Fish (IOI08_fish) C++17
0 / 100
 228 ms 25568 KB 
#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] = {};

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, m, 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*(el+1)%m*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*(el+1)%m*(nums[el]-1)%m;
                    }
                    else res = res*(el+1)%m*nums[el]%m;
                }
                ans = (ans+res)%m;
            }
        }
    }

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

    return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 15948 KB Output isn't correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 15948 KB Output isn't correct

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 15948 KB Output isn't correct

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 15948 KB Output isn't correct

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15948 KB Output is correct
2 Incorrect 9 ms 15924 KB Output isn't correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16012 KB Output is correct
2 Incorrect 222 ms 25532 KB Output isn't correct

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 15948 KB Output isn't correct

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 16076 KB Output isn't correct

Subtask #9
0 / 6.0

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

Subtask #10
0 / 6.0

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

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

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

Subtask #13
0 / 7.0

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

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 198 ms 24760 KB Output isn't correct

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 201 ms 25568 KB Output isn't correct

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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