oj.uz

Submission #363226

# Submission time Handle Problem Language Result Execution time Memory
363226 2021-02-05T10:08:57 Z negar_a Fish (IOI08_fish) C++17
100 / 100
 1255 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second
#define debug(); cerr <<"bug!"<<endl; 
 
const int maxn = 5e5 + 2;
int l[maxn], t[maxn];
int ind[maxn], big[maxn];
vector <int> vec[maxn];
vector <int> bigs;
vector <pii> v;
ll seg[maxn * 4], c[maxn];
int f, k, m;
 
int sum(ll x, ll y){
	return (x % m + y % m) % m;
//	return x + y;
}
int mul(ll x, ll y){
	return (1LL * x % m * y % m) % m;
//	return x * y;
}
void add(int l, int r, int ind, int x){
	if(l + 1 >= r){
		seg[x] = sum(seg[x], 1);
		return;
	}
	int mid = (l + r) / 2;
	if(ind < mid){
		add(l, mid, ind, x * 2);
	}else{
		add(mid, r, ind, x * 2 + 1);
	}
	seg[x] = mul(seg[x * 2], seg[x * 2 + 1]);
}
ll get(int l, int r, int L, int R, int x){
	if(l >= R || r <= L){
		return (ll)1;
	}
	if(l >= L && r <= R){
		return seg[x] % m;
	}
	int mid = (l + r) / 2;
	return mul(get(l, mid, L, R, x * 2), get(mid, r, L, R, x * 2 + 1));
}
int pt = 0;
void upd_c(int x, int i){
	while(l[v[pt].S] * 2 <= l[x]){
		int y = v[pt].S; 
		c[t[y]] ++;
		add(0, k, ind[t[y]], 1);
		pt ++;
	}
}
int find_ind(int le, int x, int r = k){
	while(le + 1 < r){
		int mid = (le + r) / 2;
		int f = bigs[mid];
		int y = v[f].S;
		if(l[y] < l[v[x].S] * 2){
			le = mid;
		}else{
			r = mid;
		}
	}
	return r;
}
 
int main(){
	fast_io;
	fill(seg, seg + maxn * 4, 1);
	fill(c, c + maxn, 1);
	
	cin >> f >> k >> m;
	for(int i = 0; i < f; i ++){
		cin >> l[i] >> t[i];
		v.pb({l[i], i});
		big[t[i]] = -1;
	}
	sort(v.begin(), v.end());
	
	for(int i = 0; i < f; i ++){
		vec[t[v[i].S]].pb(i);
	}
	int num = 0;
	for(int i = f - 1; i >= 0; i --){
		if(big[t[v[i].S]] == -1){
			big[t[v[i].S]] = i;
			ind[t[v[i].S]] = k - num - 1;
			bigs.pb(i);
			num ++;
		}
	}
	reverse(bigs.begin(), bigs.end());
	ll ans = 0;
 
	for(int i = 0; i < f; i ++){
		int x = v[i].S;
		upd_c(x, i);
		if(big[t[x]] == i){
			ll p = get(0, k, 0, ind[t[x]], 1);
			int in = find_ind(ind[t[x]], vec[t[x]][c[t[x]] - 1]);
			ll val = get(0, k, ind[t[x]] + 1, in, 1);
			ll v1 = mul(p, c[t[x]] - 1);
			ll v2 = mul(val, p);
			ans = sum(ans, sum(v1, v2));
		}
	}
	cout << ans % m;
	
	return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31724 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31724 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31724 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31724 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31724 KB Output is correct
2 Correct 20 ms 31724 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31724 KB Output is correct
2 Correct 245 ms 42076 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31724 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 31852 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 36196 KB Output is correct
2 Correct 132 ms 37348 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31852 KB Output is correct
2 Correct 24 ms 31980 KB Output is correct
3 Correct 23 ms 31852 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 38492 KB Output is correct
2 Correct 309 ms 41980 KB Output is correct
3 Correct 285 ms 43276 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 42716 KB Output is correct
2 Correct 309 ms 42844 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 38364 KB Output is correct
2 Correct 319 ms 42716 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 41820 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 43228 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 41564 KB Output is correct
2 Correct 441 ms 46172 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 763 ms 46812 KB Output is correct
2 Correct 582 ms 44252 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 47720 KB Output is correct
2 Correct 691 ms 46044 KB Output is correct
3 Correct 724 ms 50292 KB Output is correct
4 Correct 711 ms 46172 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1002 ms 49392 KB Output is correct
2 Correct 1180 ms 63148 KB Output is correct
3 Correct 988 ms 65536 KB Output is correct
4 Correct 1255 ms 65536 KB Output is correct