# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
880463 |
2023-11-29T13:04:19 Z |
josanneo22 |
Fish (IOI08_fish) |
C++17 |
|
719 ms |
62804 KB |
#include<bits/stdc++.h>
using namespace std;
#define ls p<<1
#define rs p<<1|1
const int N=5e5+500;
int t[N<<2],F,K,M,cnt[N],f[N];
set<int> S[N];
inline int chen(int x,int y){
x%=M; y%=M;
x*=y; x%=M;
return x;
}
void modify(int p,int l,int r,int x,int v){
if(l==r){
t[p]=v%M;
return;
}
int mid=(l+r)>>1;
if(x<=mid) modify(ls,l,mid,x,v);
if(x>=mid+1) modify(rs,mid+1,r,x,v);
t[p]=chen(t[ls],t[rs]);
return;
}
int query(int p,int l,int r,int ql,int qr){
if(ql<=l && r<=qr) return t[p];
int mid=(l+r)>>1,ans=1;
if(ql<=mid) chen(ans,query(ls,l,mid,ql,qr));
if(qr>=mid+1) chen(ans,query(rs,mid+1,r,ql,qr));
return ans%M;
}
struct fish{
int len,gem;
bool operator <(const fish &b){ return len<b.len;}
}a[N];
int main(){
cin>>F>>K>>M;
memset(t,1,sizeof(t));
for(int i=1;i<=F;i++)
cin>>a[i].len>>a[i].gem;
sort(a+1,a+1+F);
int T=K;
for(int i=F;i>=1;i--){
if(!cnt[a[i].gem])
cnt[a[i].gem]=T--;
a[i].gem=cnt[a[i].gem];
}
for(int i=1;i<=F;i++) cnt[i]=0;
for(int i=1;i<=F;i++){
cnt[a[i].gem]++;
S[a[i].gem].insert(i);
}
for(int i=1;i<=K;i++) cnt[i]++;
for(int i=1;i<=K;i++) modify(1,1,K,i,cnt[i]);
int ans=0;
for(int i=F,j=F;i>=1;i--){
if(*prev(S[a[i].gem].end())==i){
while(j>=1 && a[j].len*2>a[i].len){
int gem=a[j].gem;
--cnt[gem]; modify(1,1,K,gem,cnt[gem]);
j--;
}
int gem=a[i].gem;
f[gem]=j;
int x=*S[gem].upper_bound(f[gem]),l=gem,r=K,res=K;
while(l<=r){
int mid=(l+r)>>1;
if(f[mid]<x) res=mid,l=mid+1;
else r=mid-1;
}
int before=(gem==1?1:query(1,1,K,1,gem-1));
int after=(gem==res?1:query(1,1,K,gem+1,res))+(cnt[gem]-1);
ans+=chen(before,after); ans%=M;
}
}
cout<<ans<<'\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
35164 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
35288 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
35164 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
35164 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
35164 KB |
Output is correct |
2 |
Incorrect |
7 ms |
35164 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
35284 KB |
Output is correct |
2 |
Incorrect |
385 ms |
62596 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
10 ms |
35416 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
10 ms |
35420 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
160 ms |
47548 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
35420 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
263 ms |
52644 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
455 ms |
62548 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
228 ms |
52564 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
434 ms |
60180 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
567 ms |
62368 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
390 ms |
57784 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
614 ms |
60284 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
581 ms |
60044 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
719 ms |
62804 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |