제출 #252623

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
252623		alishahali1382	Fish (IOI08_fish)	C++14	75 / 100	3098 ms	24056 KiB

fish

#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=10000000000000010LL;
const int MAXN=500010, LOG=20;
int mod;

int n, m, k, u, v, x, y, t, a, b, ans;
pii A[MAXN];
int last[MAXN];
int ted[MAXN];
vector<int> vec[MAXN];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>m>>mod;
	for (int i=1; i<=n; i++) cin>>A[i].first>>A[i].second;
	sort(A+1, A+n+1);
	for (int i=1; i<=n; i++) last[A[i].second]=i, vec[A[i].second].pb(i);
	int pnt=1;
	for (int i=1; i<=n; i++){
		while (2*A[pnt].first<=A[i].first) ted[A[pnt++].second]++;
		int x=A[i].second;
		if (i!=last[x]) continue ;
		// type 1
		int bad=A[vec[x][ted[x]]].first;
		int res=1;
		for (int y=1; y<=m; y++) if (A[last[y]].first/2<bad && y!=x) res=res*(ted[y]+1ll)%mod;
		ans=(ans + res)%mod;
		
		// type 2
		if (!ted[x]) continue ;
		res=ted[x];
		for (int y=1; y<=m; y++) if (last[y]<i) res=res*(ted[y]+1ll)%mod;
		ans=(ans + res)%mod;
	}
	cout<<ans<<"\n";
	
	return 0;
}
/*
5 3 10007
2 2
2 3
4 1
5 1
8 3

4 2 10007
1 1
1 2
2 1
2 2


*/

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