Submission #594705

#TimeUsernameProblemLanguageResultExecution timeMemory
594705Bench0310Fish (IOI08_fish)C++17
100 / 100
828 ms28856 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; int mod; int add(int a,int b){return a+b-(a+b>=mod?mod:0);} int sub(int a,int b){return a-b+(a-b<0?mod:0);} int mul(int a,int b){return (a*b)%mod;} const int N=500005; int tree[4*N]; array<int,2> fish[N]; int newid[N]; bool islast[N]; int lenlast[N]; int lenprv[N]; int nxtlast[N]; int lenone[N]; void update(int idx,int l,int r,int pos,int x) { if(l==r) tree[idx]=add(tree[idx],x); else { int m=(l+r)/2; if(pos<=m) update(2*idx,l,m,pos,x); else update(2*idx+1,m+1,r,pos,x); tree[idx]=mul(tree[2*idx],tree[2*idx+1]); } } int query(int idx,int l,int r,int ql,int qr) { if(ql>qr) return 1; if(l==ql&&r==qr) return tree[idx]; int m=(l+r)/2; return mul(query(2*idx,l,m,ql,min(qr,m)),query(2*idx+1,m+1,r,max(ql,m+1),qr)); } int main() { ios::sync_with_stdio(0); cin.tie(0); int n,m; cin >> n >> m >> mod; for(int i=0;i<n;i++) for(int j=0;j<2;j++) cin >> fish[i][j]; sort(fish,fish+n); int tcnt=m; for(int i=n-1;i>=0;i--) { if(newid[fish[i][1]]==0) { newid[fish[i][1]]=tcnt--; islast[i]=1; } } for(int i=0;i<n;i++) fish[i][1]=newid[fish[i][1]]; for(int i=n-1;i>=0;i--) { auto [sz,g]=fish[i]; if(islast[i]) lenlast[g]=sz; if(2*sz>lenlast[g]) lenprv[g]=sz; if(i+1<n) nxtlast[i]=nxtlast[i+1]; if(islast[i]) nxtlast[i]=i; } for(int i=0;i<n;i++) { auto [sz,g]=fish[i]; if(2*sz<=lenlast[g]) lenone[g]=sz; } for(int i=0;i<4*N;i++) tree[i]=1; auto getlim=[&](int sz) { int p=lower_bound(fish,fish+n,array<int,2>{2*sz,0})-fish; if(p==n) return m+1; return fish[nxtlast[p]][1]; }; auto getp=[&](int l,int r)->int{return query(1,1,m,l,r);}; int res=0; int idx=0; for(int i=0;i<n;i++) { auto [sz,g]=fish[i]; if(!islast[i]) continue; while(2*fish[idx][0]<=sz) update(1,1,m,fish[idx++][1],1); int one=max(getlim(lenone[g]),g+1); int two=getlim(lenprv[g]); res=add(res,mul(getp(1,g-1),getp(g+1,two-1))); update(1,1,m,g,mod-1); res=add(res,getp(1,one-1)); update(1,1,m,g,1); } cout << res << "\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...