Submission #365078

#	Time	Username	Problem	Language	Result	Execution time	Memory
365078		Saynaa	Fish (IOI08_fish)	C++14	100 / 100	932 ms	53556 KiB

fish

#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 / 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