Submission #1016988

#TimeUsernameProblemLanguageResultExecution timeMemory
1016988huutuanFish (IOI08_fish)C++14
4 / 100
3048 ms8928 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]; vector<int> v[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)%mod; } for (int t:v[a[i].second]){ int cur=1; for (int k=1; k<=m; ++k) if (k!=a[i].second){ if (k==t) cur=cur*cnt[k]%mod; else cur=cur*(cnt[k]+1)%mod; } ans=(ans+cur)%mod; } { for (int k=1; k<=m; ++k){ if (f[k]+1>cnt[k]) v[k].push_back(a[i].second); } } } 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...