oj.uz

Submission #880460

# Submission time Handle Problem Language Result Execution time Memory
880460 2023-11-29T13:01:01 Z josanneo22 Fish (IOI08_fish) C++17
88 / 100
 758 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]*t[rs])%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);
	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);
			ans+=before*after; ans%=M;
		}
	}
	cout<<ans<<'\n';
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 35160 KB Output is correct

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 35532 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35160 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 35260 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35160 KB Output is correct
2 Correct 361 ms 62372 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 153 ms 47520 KB Output is correct
2 Correct 171 ms 50260 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 35416 KB Output is correct
2 Correct 11 ms 35676 KB Output is correct
3 Correct 10 ms 35420 KB Output is correct

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 52700 KB Output is correct
2 Correct 436 ms 65536 KB Output is correct
3 Incorrect 390 ms 65536 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 62428 KB Output is correct
2 Correct 439 ms 65536 KB Output is correct

Subtask #13
7.0 / 7.0

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

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 60244 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 62572 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 57680 KB Output is correct
2 Correct 564 ms 65536 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 60068 KB Output is correct
2 Correct 421 ms 57272 KB Output is correct

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 60500 KB Output is correct
2 Correct 597 ms 65536 KB Output is correct
3 Incorrect 497 ms 65536 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 62548 KB Output is correct
2 Correct 713 ms 65536 KB Output is correct
3 Correct 648 ms 65536 KB Output is correct
4 Correct 758 ms 65536 KB Output is correct