# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
92221 | 2019-01-02T05:50:51 Z | diamond_duke | Fish (IOI08_fish) | C++11 | 1177 ms | 46100 KB |
#include <algorithm> #include <utility> #include <cstdio> #include <vector> using ll = long long; int idx[500005], seg[1000005]; bool vis[500005]; std::pair<int, int> arr[500005]; std::vector<int> vec[500005]; int main() { // freopen("IOI2008-D1T3.in", "r", stdin); int n, MOD, cnt = 0, 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 (!vis[arr[i].second]) { vis[arr[i].second] = true; idx[arr[i].second] = cnt++; } arr[i].second = idx[arr[i].second]; } for (int i = 0; i < n; i++) vec[arr[i].second].push_back(i); for (int i = 0; i < cnt << 1; i++) seg[i] = 1; auto modify = [&] (int pos, int x) { for (seg[pos += cnt] += x; pos; pos >>= 1) seg[pos >> 1] = (ll)seg[pos] * seg[pos ^ 1] % MOD; }; auto query = [&] (int l, int r) { int res = 1; for (l += cnt, r += cnt + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) res = (ll)res * seg[l++] % MOD; if (r & 1) res = (ll)res * seg[--r] % MOD; } return res; }; for (int i = 0, j = 0; i < n; i++) { while (j < n && arr[j].first << 1 <= arr[i].first) modify(arr[j++].second, 1); if (vec[arr[i].second].back() != i) continue; modify(arr[i].second, -1); ans = (ans + query(arr[i].second, cnt - 1)) % MOD; int pos = -1; for (int x : vec[arr[i].second]) { if (-1 == pos && arr[x].first << 1 > arr[i].first) pos = x; } int l = 0, r = arr[i].second, res = -1; while (l <= r) { int m = l + r >> 1; if (arr[pos].first << 1 > arr[vec[m].back()].first) { res = m; r = m - 1; } else l = m + 1; } ans = (ans + (ll)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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 12152 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 12024 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 12152 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 12024 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 12024 KB | Output is correct |
2 | Correct | 10 ms | 12024 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 12152 KB | Output is correct |
2 | Correct | 193 ms | 24572 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 12024 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 12152 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 87 ms | 17272 KB | Output is correct |
2 | Correct | 116 ms | 18608 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 12152 KB | Output is correct |
2 | Correct | 16 ms | 12280 KB | Output is correct |
3 | Correct | 15 ms | 12280 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 144 ms | 20520 KB | Output is correct |
2 | Correct | 299 ms | 25044 KB | Output is correct |
3 | Correct | 243 ms | 25668 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 248 ms | 24824 KB | Output is correct |
2 | Correct | 238 ms | 26060 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 139 ms | 20728 KB | Output is correct |
2 | Correct | 269 ms | 25804 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 261 ms | 24936 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 307 ms | 27000 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 266 ms | 24568 KB | Output is correct |
2 | Correct | 389 ms | 29860 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 659 ms | 29944 KB | Output is correct |
2 | Correct | 511 ms | 25944 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 565 ms | 28848 KB | Output is correct |
2 | Correct | 532 ms | 29944 KB | Output is correct |
3 | Correct | 629 ms | 32740 KB | Output is correct |
4 | Correct | 579 ms | 29944 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 913 ms | 33016 KB | Output is correct |
2 | Correct | 1096 ms | 45304 KB | Output is correct |
3 | Correct | 962 ms | 46100 KB | Output is correct |
4 | Correct | 1177 ms | 41720 KB | Output is correct |