Submission #1103025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103025		_rain_	Fish (IOI08_fish)	C++14	0 / 100	109 ms	14724 KiB

fish

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = (int)5e5;
int f,MOD,k,l[N+2],da[N+2];
bool ex[N+2],id[N+2],used[N+2];
struct CTDL{
	int l,da;
	bool operator < (const CTDL& other) const{
		return l<other.l;
	}
} p[N+2];
int add(int a,int b){
	return a+b>=MOD?a+b-MOD:a+b;
}
int sub(int a,int b){
	return a-b<0?a-b+MOD:a-b;
}
int mul(int a,int b){
	return (ll)a*b%MOD;
}
int power(int a,int b){
	int res=1;
	for (;b;b>>=1,a=mul(a,a)){
		if (b&1) res=mul(res,a);
	}
	return res;
}

#define name "main"
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin>>f>>k>>MOD;
	for (int i = 1; i <= f; ++i){
		cin>>p[i].l>>p[i].da;
	}
	sort(p+1,p+f+1);
	for (int i = f; i >= 1; --i){
		if (!used[p[i].da]){
			used[p[i].da]=true;
			id[i]=true;
		}
	}
	memset(used,0,sizeof used);
	int cnt=0,ans=0,l=1;
	for (int i = 1; i <= f; ++i){
		while (l<=i&&p[l].l*2<=p[i].l){
			if (!used[p[l].da]){
				used[p[l].da]=true;
				++cnt;
			}
			++l;
		}
		if (id[i]){
			ans=add(ans,power(2,cnt));
		}
	}
	cout<<ans;
	exit(0);	
}

• Subtask 1: 0 / 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