제출 #91808

#제출 시각아이디문제언어결과실행 시간메모리
91808diamond_dukeFish (IOI08_fish)C++11
93 / 100
789 ms46456 KiB
#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; }

컴파일 시 표준 에러 (stderr) 메시지

fish.cpp: In function 'int main()':
fish.cpp:67:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int m = l + r >> 1;
            ~~^~~
fish.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%*d%d", &n, &MOD);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
fish.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &arr[i].first, &arr[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...