oj.uz

Submission #880464

# Submission time Handle Problem Language Result Execution time Memory
880464 2023-11-29T13:05:48 Z josanneo22 Fish (IOI08_fish) C++17
0 / 100
 744 ms 60424 KB 
#include<bits/stdc++.h>
using namespace std;

#define ls p<<1
#define rs p<<1|1
const int N=5e5+50;
int t[N<<2],F,K,M,cnt[N],f[N];
set<int> S[N];
int chen(int x,int y){
	return ((x%M)*(y%M))%M;
}
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]=chen(t[ls],t[rs]);
	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) chen(ans,query(ls,l,mid,ql,qr));
	if(qr>=mid+1) chen(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;
	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+=chen(before,after); ans%=M;
		}
	}
	cout<<ans<<'\n';
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 31064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 31068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 31068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 31068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31068 KB Output is correct
2 Incorrect 6 ms 31068 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31064 KB Output is correct
2 Incorrect 391 ms 58484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 31064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 31324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 162 ms 43380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 31324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 258 ms 48468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 459 ms 58468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 238 ms 48464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 479 ms 55888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 593 ms 58480 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 452 ms 53744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 645 ms 58180 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 540 ms 58180 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 744 ms 60424 KB Output isn't correct
2 Halted 0 ms 0 KB -