# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
923220 | 2024-02-07T00:23:47 Z | math_rabbit_1028 | Fish (IOI08_fish) | C++14 | 3000 ms | 30292 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++) { dp[i][0] = dp[i][1] = 1; int cnt = upper_bound(vec[i].begin(), vec[i].end(), vec[i].back()/2) - vec[i].begin(); int q = 0; 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] - 1; ans %= MOD; } cout << ans << "\n"; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 15704 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 15708 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 15704 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 15708 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 15964 KB | Output is correct |
2 | Incorrect | 4 ms | 15904 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 15708 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 15704 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 15964 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 36 ms | 19664 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 31 ms | 15960 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 77 ms | 22068 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 94 ms | 24912 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 154 ms | 22284 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1109 ms | 25124 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2549 ms | 28820 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 3043 ms | 24916 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 3072 ms | 28412 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 3054 ms | 27368 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 3044 ms | 30292 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |