# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
53862 | 2018-07-01T12:26:28 Z | baactree | Fish (IOI08_fish) | C++17 | 1039 ms | 31736 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; while (ri>=0&&(vec[ri].empty()||arr[vec[ri].back()].first < le))ri--; ans = (ans + query(ri + 1, 500004)) % mod; update(arr[idx].second, temp); } } printf("%lld\n", ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 26 ms | 20088 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 25 ms | 20088 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 25 ms | 20252 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 26 ms | 20252 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 27 ms | 20252 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 27 ms | 20452 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 29 ms | 20452 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 32 ms | 20452 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 151 ms | 23188 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 35 ms | 23188 KB | Output is correct |
2 | Correct | 35 ms | 23188 KB | Output is correct |
3 | Incorrect | 35 ms | 23188 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 220 ms | 24740 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 389 ms | 27048 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 211 ms | 27048 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 380 ms | 27048 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 414 ms | 27812 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 340 ms | 27812 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 719 ms | 29892 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 710 ms | 30736 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1039 ms | 31736 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |