oj.uz

Submission #365078

# Submission time Handle Problem Language Result Execution time Memory
365078 2021-02-10T20:59:48 Z Saynaa Fish (IOI08_fish) C++14
100 / 100
 932 ms 53556 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAXN = 5e5 + 5;
int n, k;
int mark[MAXN], x[MAXN];
int mx[MAXN];
bool big[MAXN];
ll res, mod;
pair< int, int> a[MAXN];
vector< int > vec[MAXN];
ll seg[MAXN * 3];

void add(int ind, int val, int b = 0, int e = k, int id = 1){
	if(b + 1 == e){
		seg[id] += val, seg[id] %= mod;
		return;
	}
	int mid = (b + e)/2;
	if(ind < mid)
		add(ind, val, b, mid, id*2);
	else add(ind, val, mid, e, id*2 + 1);
	seg[id] = (seg[id*2] * seg[id*2 + 1])%mod;
}

ll get(int l, int r, int b = 0, int e = k, int id = 1){
	if( r <= b || e <= l)
		return 1;
	if( l <= b && e <= r)
		return seg[id];
	int mid = (b + e)/2;
	return get(l, r, b, mid, id*2) * get(l, r, mid, e, id*2 + 1) % mod;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> k >> mod;
	for(int i = 0; i < n; i ++)
		cin >> a[i].first >> a[i].second, a[i].second --;
	sort(a, a + n);
	for(int i = 0; i < k; i ++)
		add(i, 1), mark[i] = -1;
	int id = k - 1;
	for(int i = n - 1; i >= 0; i --){
		if(mark[a[i].second] < 0){
			mark[a[i].second] = id;
			mx[id] = a[i].first;
			vec[id].push_back(a[i].first);
			big[i] = true;
			id --;	
		}
		else
			vec[mark[a[i].second]].push_back(a[i].first);
	}
	for(int i = 0; i < k; i ++) reverse(vec[i].begin(), vec[i].end());
	id = 0;
	for(int i = 0; i < n; i ++){
		if( !big[i] ) continue;
		while(id < i){
			if(2*a[id].first > a[i].first)
				break;
			x[mark[a[id].second]] ++;
			add(mark[a[id].second], 1);
			id ++;
		}
		res = (res + get(0, mark[a[i].second] + 1)) % mod;
		int it = lower_bound(mx, mx + k, vec[mark[a[i].second]][x[mark[a[i].second]]] * 2) - mx;
		res = (res + get(0, mark[a[i].second])*(get(mark[a[i].second] + 1, it) + mod - 1)%mod)%mod;
		
	}
	cout << res << endl;
	return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12140 KB Output is correct
2 Correct 171 ms 19180 KB Output is correct

Subtask #7
6.0 / 6.0

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

Subtask #8
6.0 / 6.0

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

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 15212 KB Output is correct
2 Correct 115 ms 18884 KB Output is correct

Subtask #10
6.0 / 6.0

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

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 16492 KB Output is correct
2 Correct 262 ms 25384 KB Output is correct
3 Correct 221 ms 25692 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 19180 KB Output is correct
2 Correct 233 ms 26476 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 16876 KB Output is correct
2 Correct 235 ms 26136 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 19052 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 20332 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 19308 KB Output is correct
2 Correct 332 ms 32108 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 27244 KB Output is correct
2 Correct 403 ms 30188 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 28012 KB Output is correct
2 Correct 448 ms 32496 KB Output is correct
3 Correct 514 ms 37064 KB Output is correct
4 Correct 458 ms 32484 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 710 ms 29676 KB Output is correct
2 Correct 932 ms 53556 KB Output is correct
3 Correct 723 ms 52564 KB Output is correct
4 Correct 924 ms 50084 KB Output is correct