oj.uz

Submission #252861

# Submission time Handle Problem Language Result Execution time Memory
252861 2020-07-26T11:14:07 Z alishahali1382 Fish (IOI08_fish) C++14
100 / 100
 730 ms 43512 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16000 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16000 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16000 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16000 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16000 KB Output is correct
2 Correct 9 ms 16000 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16000 KB Output is correct
2 Correct 184 ms 22536 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16000 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16128 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 18876 KB Output is correct
2 Correct 101 ms 19424 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16128 KB Output is correct
2 Correct 11 ms 16128 KB Output is correct
3 Correct 11 ms 16128 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 20440 KB Output is correct
2 Correct 225 ms 22400 KB Output is correct
3 Correct 216 ms 22772 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 22776 KB Output is correct
2 Correct 221 ms 23160 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 20344 KB Output is correct
2 Correct 223 ms 22892 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 22648 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 23844 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 22264 KB Output is correct
2 Correct 357 ms 26104 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 27256 KB Output is correct
2 Correct 341 ms 25720 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 28024 KB Output is correct
2 Correct 402 ms 26360 KB Output is correct
3 Correct 395 ms 30692 KB Output is correct
4 Correct 391 ms 26604 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 29564 KB Output is correct
2 Correct 520 ms 43512 KB Output is correct
3 Correct 713 ms 41592 KB Output is correct
4 Correct 730 ms 38776 KB Output is correct