Submission #1016971

#TimeUsernameProblemLanguageResultExecution timeMemory
1016971huutuanFish (IOI08_fish)C++14
0 / 100
36 ms1416 KiB
#include<bits/stdc++.h> using namespace std; const int N=7000+10; int n, m, mod, mx[N], cnt[N], mult[N], f[N]; pair<int, int> a[N]; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m >> mod; for (int i=1; i<=n; ++i) cin >> a[i].first >> a[i].second; sort(a+1, a+n+1); for (int i=1; i<=n; ++i) mx[a[i].second]=i, ++cnt[a[i].second]; for (int i=1; i<=n; ++i) if (a[i].first*2<=a[mx[a[i].second]].first) ++f[a[i].second]; int ans=0; for (int i=n, j=n; i>=1; --i) if (mx[a[i].second]==i){ while (j && a[j].first*2>a[i].first){ --cnt[a[j].second]; --j; } { int cur=1; for (int k=1; k<=m; ++k) if (mx[k]<=i) cur=cur*(cnt[k]+1)%mod; ans=(ans+cur*(1-mult[a[i].second]))%mod; } { int cur=1; for (int k=1; k<=m; ++k) if (k!=a[i].second) cur=cur*(cnt[k]+1)%mod; ans=(ans+cur*mult[a[i].second])%mod; } { for (int k=1; k<=m; ++k){ if (f[k]>cnt[k]) ++mult[k]; } } } cout << ans << '\n'; return 0; }
#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...