Submission #1017011

#TimeUsernameProblemLanguageResultExecution timeMemory
1017011huutuanFish (IOI08_fish)C++14
32 / 100
3042 ms2204 KiB
#include<bits/stdc++.h> using namespace std; const int N=7000+10; int n, m, mod, mx[N], cnt[N], f[N], vis[N], cnt2[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], f[a[i].second]=1; 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 k:v[a[i].second]) vis[k]=0; { for (int k=1; k<=m; ++k) if (mx[k]<i){ if (f[k]>cnt[k]){ int j2=j; while (j && a[j].first*2>a[mx[k]].first){ --cnt[a[j].second]; --j; } { int cur=1; for (int t=1; t<=m; ++t) if (mx[t]<=i){ if (t==a[i].second) cur=cur*cnt[t]%mod; else if (t!=k) cur=cur*(cnt[t]+1)%mod; } ans=(ans+cur)%mod; } while (j!=j2){ ++j; ++cnt[a[j].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...