# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
53863 | 2018-07-01T12:33:13 Z | baactree | Fish (IOI08_fish) | C++17 | 1214 ms | 31900 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll tree[1 << 20]; int sz = 1 << 19; int n, m, mod; pair<int, int> arr[500005]; vector<int> vec[500005]; bool chk[500005]; int t[500005]; void update(int idx, int val) { idx += sz; tree[idx] = val; idx /= 2; while (idx) { tree[idx] = tree[idx * 2] * tree[idx * 2 + 1] % mod; idx /= 2; } } ll query(int le, int ri) { le += sz; ri += sz; ll ret = 1; while (le <= ri) { if (le & 1)ret = ret * tree[le++] % mod; if (!(ri & 1))ret = ret * tree[ri--] % mod; le /= 2; ri /= 2; } return ret; } int main() { scanf("%d%d%d", &n, &m, &mod); for (int i = 0; i < n; i++) scanf("%d%d", &arr[i].first, &arr[i].second); sort(arr, arr + n); int cnt = 0; for (int i = n - 1; i >= 0; i--) { if (!chk[arr[i].second]) { t[arr[i].second] = ++cnt; chk[arr[i].second] = true; } } for (int i = 0; i < n; i++) { arr[i].second = t[arr[i].second]; vec[arr[i].second].push_back(i); } ll ans = 0; for (int i = 0; i < 500005; i++) tree[i + sz] = 1; for (int i = sz - 1; i; i--) tree[i] = tree[i * 2] * tree[i * 2 + 1] % mod; int idx = 0; int ri = 500004; for (int i = 0; i < n; i++) { while (arr[idx].first * 2 <= arr[i].first) { update(arr[idx].second, tree[arr[idx].second + sz] + 1); idx++; } if (vec[arr[i].second].back()==i) { ans = (ans + query(arr[i].second, 500004)) % mod; ll temp = tree[arr[idx].second + sz]; update(arr[idx].second, 1); int it = -1; for (auto x : vec[arr[i].second]) { if (arr[x].first > arr[i].first / 2) { it = x; break; } } int le = arr[it].first * 2; int l, r, mid, ri; l = 1; r = arr[i].second; while (l <= r) { mid = (l + r) / 2; if (arr[vec[mid].back()].first < le) { ri = mid; r = mid - 1; } else l = mid + 1; } ans = (ans + query(ri, 500004)) % mod; update(arr[idx].second, temp); } } printf("%lld\n", ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 31 ms | 20088 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 27 ms | 20200 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 24 ms | 20200 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 31 ms | 20332 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 27 ms | 20348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 29 ms | 20348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 27 ms | 20348 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 27 ms | 20428 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 159 ms | 23220 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 33 ms | 23220 KB | Output is correct |
2 | Incorrect | 42 ms | 23220 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 231 ms | 24812 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 443 ms | 27080 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 204 ms | 27080 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 385 ms | 27080 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 506 ms | 27768 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 452 ms | 27768 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1133 ms | 29932 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 729 ms | 30816 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1214 ms | 31900 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |