# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
91808 | 2018-12-30T06:28:06 Z | diamond_duke | Fish (IOI08_fish) | C++11 | 789 ms | 46456 KB |
#include <algorithm> #include <utility> #include <cstdio> #include <vector> std::pair<int, int> arr[500005]; int idx[500005], seg[1000005], cnt, MOD; bool app[500005]; std::vector<int> vec[500005]; void modify(int pos, int x) { for (seg[pos += cnt] += x; pos; pos >>= 1) seg[pos >> 1] = seg[pos] * seg[pos ^ 1] % MOD; } int query(int l, int r) { int res = 1; for (l += cnt, r += cnt + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) res = res * seg[l++] % MOD; if (r & 1) res = res * seg[--r] % MOD; } return res; } int main() { int n, ans = 0; scanf("%d%*d%d", &n, &MOD); for (int i = 0; i < n; i++) scanf("%d%d", &arr[i].first, &arr[i].second); std::sort(arr, arr + n); for (int i = n - 1; i >= 0; i--) { if (app[arr[i].second]) continue; app[arr[i].second] = true; idx[arr[i].second] = cnt++; } for (int i = 0; i < n; i++) { arr[i].second = idx[arr[i].second]; vec[arr[i].second].push_back(i); } for (int i = 0; i < cnt << 1; i++) seg[i] = 1; for (int i = 0, cur = 0; i < n; i++) { while (arr[cur].first << 1 <= arr[i].first) modify(arr[cur++].second, 1); if (vec[arr[i].second].back() != i) continue; modify(arr[i].second, -1); (ans += query(arr[i].second, cnt - 1)) %= MOD; int pos = -1; for (int x : vec[arr[i].second]) { if (arr[x].first << 1 > arr[i].first) { pos = x; break; } } int l = 0, r = arr[i].second, res = -1; while (l <= r) { int m = l + r >> 1; if (arr[vec[m].back()].first < arr[pos].first << 1) { r = m - 1; res = m; } else l = m + 1; } (ans += query(res, arr[i].second - 1) * query(arr[i].second + 1, cnt - 1)) %= MOD; modify(arr[i].second, 1); } printf("%d\n", ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 12072 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 12152 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 12024 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 12024 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 12024 KB | Output is correct |
2 | Correct | 12 ms | 12152 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 12024 KB | Output is correct |
2 | Correct | 181 ms | 24656 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 12152 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 12152 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 81 ms | 17304 KB | Output is correct |
2 | Correct | 104 ms | 18628 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 12152 KB | Output is correct |
2 | Correct | 15 ms | 12280 KB | Output is correct |
3 | Correct | 14 ms | 12280 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 131 ms | 20496 KB | Output is correct |
2 | Incorrect | 222 ms | 25204 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 188 ms | 25012 KB | Output is correct |
2 | Correct | 219 ms | 26156 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 119 ms | 20728 KB | Output is correct |
2 | Correct | 229 ms | 25952 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 222 ms | 24924 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 247 ms | 27092 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 216 ms | 24508 KB | Output is correct |
2 | Correct | 364 ms | 29804 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 533 ms | 29992 KB | Output is correct |
2 | Correct | 374 ms | 25976 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 421 ms | 28920 KB | Output is correct |
2 | Correct | 445 ms | 30120 KB | Output is correct |
3 | Correct | 431 ms | 32740 KB | Output is correct |
4 | Correct | 458 ms | 29808 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 658 ms | 33016 KB | Output is correct |
2 | Correct | 652 ms | 45220 KB | Output is correct |
3 | Correct | 606 ms | 46456 KB | Output is correct |
4 | Correct | 789 ms | 41728 KB | Output is correct |