oj.uz

Submission #880467

# Submission time Handle Problem Language Result Execution time Memory
880467 2023-11-29T13:07:28 Z josanneo22 Fish (IOI08_fish) C++17
100 / 100
 930 ms 65536 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];
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';
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35164 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35276 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35164 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35164 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35164 KB Output is correct
2 Correct 7 ms 35272 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35164 KB Output is correct
2 Correct 418 ms 62624 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35164 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 35420 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 47620 KB Output is correct
2 Correct 199 ms 50256 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 35472 KB Output is correct
2 Correct 12 ms 35516 KB Output is correct
3 Correct 11 ms 35420 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 52816 KB Output is correct
2 Correct 455 ms 65536 KB Output is correct
3 Correct 508 ms 65536 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 62368 KB Output is correct
2 Correct 510 ms 65536 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 52644 KB Output is correct
2 Correct 553 ms 65536 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 60076 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 62368 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 57896 KB Output is correct
2 Correct 690 ms 65536 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 60064 KB Output is correct
2 Correct 461 ms 52644 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 596 ms 60500 KB Output is correct
2 Correct 682 ms 65536 KB Output is correct
3 Correct 610 ms 65536 KB Output is correct
4 Correct 683 ms 65536 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 758 ms 62548 KB Output is correct
2 Correct 853 ms 65536 KB Output is correct
3 Correct 838 ms 65536 KB Output is correct
4 Correct 930 ms 65536 KB Output is correct