Submission #252861

#	Time	Username	Problem	Language	Result	Execution time	Memory
252861		alishahali1382	Fish (IOI08_fish)	C++14	100 / 100	730 ms	43512 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], col[MAXN], koj[MAXN];
int ted[MAXN], seg[MAXN<<1];
vector<int> vec[MAXN];

void Set(int pos, int val){
	seg[pos+=m]=val%mod;
	for (; pos>1; pos>>=1) seg[pos>>1]=seg[pos]*seg[pos^1]%mod;
}
int Get(int l, int r){
	int res=1;
	for (l+=m, r+=m; l<r; l>>=1, r>>=1){
		if (l&1) res=res*seg[l++]%mod;
		if (r&1) res=res*seg[--r]%mod;
	}
	return res;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	fill(seg, seg+2*MAXN, 1);
	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);
	for (int i=1; i<=m; i++) col[i]=i;
	sort(col+1, col+m+1, [&](int i, int j){
		return last[i]<last[j];
	});
	for (int i=1; i<=m; i++) koj[col[i]]=i;
	
	int pnt=1;
	for (int i=1; i<=n; i++){
		while (2*A[pnt].first<=A[i].first){
			int c=A[pnt++].second;
			ted[c]++;
			Set(koj[c], ted[c]+1);
		}
		int x=A[i].second;
		if (i!=last[x]) continue ;
		// type 1
		int bad=A[vec[x][ted[x]]].first;
		int dwn=0, up=m+1;
		while (up-dwn>1){
			int mid=(dwn+up)>>1;
			if (A[last[col[mid]]].first/2<bad) dwn=mid;
			else up=mid;
		}
		Set(koj[x], 1);
		ll res=Get(1, up);
		Set(koj[x], ted[x]+1);
		ans=(ans + res)%mod;
		
		// type 2
		if (!ted[x]) continue ;
		res=1ll*ted[x]*Get(1, koj[x])%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: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5