oj.uz

Submission #473630

# Submission time Handle Problem Language Result Execution time Memory
473630 2021-09-15T18:29:41 Z OttoTheDino Fish (IOI08_fish) C++17
17 / 100
 253 ms 31728 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] = {}, 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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15948 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15948 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15884 KB Output is 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 10 ms 15948 KB Output is correct
2 Incorrect 8 ms 15920 KB Output isn't correct

Subtask #6
0 / 5.0

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

Subtask #7
0 / 6.0

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

Subtask #8
0 / 6.0

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

Subtask #9
0 / 6.0

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

Subtask #10
0 / 6.0

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

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

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

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 130 ms 20752 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 23068 KB Output isn't correct

Subtask #15
0 / 5.0

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

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 22232 KB Output is correct
2 Correct 185 ms 31728 KB Output is correct

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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