Submission #416066

#	Time	Username	Problem	Language	Result	Execution time	Memory
416066		Antekb	Fish (IOI08_fish)	C++14	4 / 100	3098 ms	9900 KiB

fish

#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
const int N=5e5+5;
int tab[N], czy[N], ile[N];
int m;
typedef long long ll;
int main(){
	int n, k;
	cin>>n>>k>>m;
	for(int i=0; i<k; i++)tab[i]=1;
	vector<pair<int, int> > V(n);
	for(auto &i:V)cin>>i.st>>i.nd, i.nd--;
	sort(V.begin(), V.end());
	int wsk=0;
	while(V[wsk].st*2<=V.back().st){
		tab[V[wsk].nd]++;
		ile[V[wsk].nd]++;
		wsk++;
	}
	int ans=0;
	for(int i=n-1; i>=0; i--){
		if(czy[V[i].nd])continue;
		while(wsk && V[wsk-1].st*2>V[i].st){
			tab[V[--wsk].nd]--;
		}
		//for(int j=0; j<k; j++)cout<<tab[j]<<" ";
		//cout<<"\n";
		int t=1;
		for(int j=0; j<k; j++){
			if(!czy[j])t=(t*1ll*tab[j])%m;
		}
		ans+=t;
		//cout<<t<<" ";
		if(i+1-n && tab[V[i].nd]>ile[V[i].nd]){
			t=1;
			int u=1;
			for(int j=0; j<k; j++){
				if(j!=V[i].nd && !czy[j])t=(t*1ll*tab[j])%m;
				if(czy[j])u=(u*1ll*tab[j])%m;
			}
			ans+=(t*1ll*(u-1))%m;
			//cout<<t*(u-1)<<" ";
		}
		czy[V[i].nd]=1;
		//cout<<"\n";
	}
	cout<<((ans%m)+m)%m;
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6
• Subtask 10: 0 / 6
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 7
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5