# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
923221 | 2024-02-07T00:39:47 Z | math_rabbit_1028 | Fish (IOI08_fish) | C++14 | 3000 ms | 25940 KB |
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; typedef long long ll; int n, k, MOD; vector<int> vec[505050]; ll dp[505050][2]; int p[505050]; bool compare(vector<int> A, vector<int> B) { return A.back() > B.back(); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> k >> MOD; for (int i = 1; i <= n; i++) { int l, t; cin >> l >> t; vec[t].push_back(l); } for (int i = 1; i <= k; i++) sort(vec[i].begin(), vec[i].end()); sort(vec + 1, vec + k + 1, compare); for (int j = 1; j <= k; j++) p[j] = vec[j].size(); for (int i = 1; i <= k; i++) { int cnt = upper_bound(vec[i].begin(), vec[i].end(), vec[i].back()/2) - vec[i].begin(); int q = 0; dp[i][0] = 1; dp[i][1] = cnt; for (int j = k; j >= 1; j--) { if (i == j) continue; while (q < vec[i].size() && vec[i][q] <= vec[j].back()/2) q++; while (p[j] > 0 && vec[j][p[j]-1] > vec[i].back()/2) p[j]--; if (i < j) { dp[i][0] = dp[i][0]*(1+p[j])%MOD; dp[i][1] = dp[i][1]*(1+p[j])%MOD; } else { if (q > cnt) continue; dp[i][0] = dp[i][0]*(1+p[j])%MOD; } } // cout << dp[i][0] << " " << dp[i][1] << "\n"; } ll ans = 0; for (int i = 1; i <= k; i++) { ans += dp[i][0] + dp[i][1]; ans %= MOD; } cout << ans << "\n"; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 15708 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 15704 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 15708 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 15708 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 15704 KB | Output is correct |
2 | Correct | 4 ms | 15704 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 15708 KB | Output is correct |
2 | Correct | 93 ms | 24324 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 15708 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 15704 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 48 ms | 17336 KB | Output is correct |
2 | Correct | 50 ms | 20420 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 32 ms | 15708 KB | Output is correct |
2 | Correct | 12 ms | 15964 KB | Output is correct |
3 | Correct | 26 ms | 16220 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 71 ms | 17864 KB | Output is correct |
2 | Correct | 169 ms | 25048 KB | Output is correct |
3 | Correct | 176 ms | 25668 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 91 ms | 18860 KB | Output is correct |
2 | Correct | 145 ms | 25940 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 148 ms | 18080 KB | Output is correct |
2 | Correct | 481 ms | 25808 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1144 ms | 18800 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2588 ms | 21688 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 3038 ms | 18708 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 3017 ms | 21208 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 3054 ms | 22384 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 3023 ms | 22324 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |