# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
776536 | jamezzz | Fish (IOI08_fish) | C++17 | 1106 ms | 57492 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define LINF 1023456789123456789
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,int> li;
#define maxn 500005
#define maxk 7005
int n,k,m,cnt[maxk],bad[maxk];
bool num[maxk][maxk];
ll mn[maxn];
vector<ii> v;
int main(){
sf("%d%d%d",&n,&k,&m);
for(int i=0;i<n;++i){
int l,c;
sf("%d%d",&l,&c);
v.pb({l,c});
++cnt[c];
}
sort(all(v));
int ptr=n-1;
ll ans=0;
fill(mn,mn+n+1,1);
for(int i=n-1;i>=0;--i){
int c=v[i].se;
if(bad[c])continue;
while(ptr>=0&&v[i].fi<2*v[ptr].fi){
--cnt[v[ptr].se];
--ptr;
}
vector<int> undo;
for(int j=1;j<=k;++j){
if(c==j)continue;
if(!bad[j]||num[j][c]){
int x=0;
if(bad[j])x=cnt[j];
mn[x+1]*=(cnt[j]+1);
mn[x+1]%=m;
undo.pb(x+1);
if(!bad[j])num[j][c]=false;
}
}
ll add=1;
for(int j=1;j<=cnt[c]+1;++j){
add*=mn[j];
add%=m;
ans+=add;
ans%=m;
}
for(int x:undo)mn[x]=1;
fill(num[c]+1,num[c]+k+1,true);
bad[c]=1;
}
pf("%lld\n",ans);
}
/*
5
3
7
2 2
4 1
8 3
4 1
2 3
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |