oj.uz

Submission #880462

# Submission time Handle Problem Language Result Execution time Memory
880462 2023-11-29T13:01:53 Z josanneo22 Fish (IOI08_fish) C++17
44 / 100
 310 ms 65536 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#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];

signed 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 8 ms 42588 KB Output is correct

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 42712 KB Output is correct
2 Runtime error 275 ms 65536 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #7
6.0 / 6.0

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

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 42844 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 57800 KB Output is correct
2 Correct 174 ms 62548 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 42752 KB Output is correct
2 Correct 12 ms 43100 KB Output is correct
3 Correct 11 ms 43100 KB Output is correct

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 215 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 257 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 171 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 268 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 296 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 229 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 280 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 225 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 310 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -