Submission #880467

#TimeUsernameProblemLanguageResultExecution timeMemory
880467josanneo22Fish (IOI08_fish)C++17
100 / 100
930 ms65536 KiB
#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]; 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]=((t[ls]%M)*(t[rs]%M))%M; 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) ans*=query(ls,l,mid,ql,qr); ans%=M; if(qr>=mid+1) 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); before%=M; after%=M; ans+=before*after; ans%=M; } } cout<<ans<<'\n'; }
#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...