제출 #788446

#제출 시각아이디문제언어결과실행 시간메모리
788446tatyamFish (IOI08_fish)C++17
0 / 100
122 ms7036 KiB
#include <bits/stdc++.h> using namespace std; int M; struct mint { int x = 0; mint& operator+=(mint a) { x += a.x; if(x >= M) x -= M; return *this; } mint operator+(mint a) const { return mint{*this} += a; } }; struct Counter { vector<int> A; int kind = 0; Counter(int n): A(n) {} void add(int x) { if(A[x]++ == 0) kind++; } void del(int x) { if(--A[x] == 0) kind--; } }; int main() { cin.tie(0)->sync_with_stdio(0); int F, K; cin >> F >> K >> M; vector<pair<int, int>> fish(F); for(auto& [L, J] : fish) { cin >> L >> J; J--; } sort(fish.begin(), fish.end(), greater<>{}); vector<mint> pow2(F + 1); pow2[0] = {1}; for(int i = 0; i < F; i++) pow2[i + 1] = pow2[i] + pow2[i]; mint ans = {0}; while(fish.size()) { const auto [L0, J0] = fish[0]; const auto half = partition_point(fish.begin(), fish.end(), [L0 = L0](pair<int, int> f) { return f.first * 2 > L0; }); Counter jewel(K); for_each(half, fish.end(), [&, L0 = L0](pair<int, int> f) { auto [L, J] = f; if(L * 2 <= L0) jewel.add(J); }); jewel.add(J0); ans += pow2[jewel.kind - 1]; vector<bool> counted(jewel.A.begin(), jewel.A.end()); jewel.del(J0); for(auto p = fish.begin(), q = half; p != fish.end(); p++) { const auto [L1, J1] = *p; if(L1 * 2 <= L0) break; if(counted[J1]) continue; while(q != fish.end()) { const auto [L2, J2] = *q; if(L2 * 2 > L1) { jewel.del(J2); q++; } else break; } jewel.add(J1); ans += pow2[jewel.kind - 1]; jewel.del(J1); counted[J1] = 1; } fish.erase(remove_if(fish.begin(), fish.end(), [&](pair<int, int> f) { return counted[f.second]; }), fish.end()); } cout << ans.x << endl; }
#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...