Submission #363224

#	Time	Username	Problem	Language	Result	Execution time	Memory
363224		negar_a	Fish (IOI08_fish)	C++17	89 / 100	1180 ms	64988 KiB

fish

#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

const int maxn = 5e5 + 2;
ll l[maxn], t[maxn];
int ind[maxn], big[maxn];
vector <int> vec[maxn];
vector <int> bigs;
vector <pii> v;
ll seg[maxn * 4];
int c[maxn];
int f, k, m;

ll sum(ll x, ll y){
	return (x % m + y % m) % m;
//	return x + y;
}
ll 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){
//	debug();
	while(le + 1 < r){
		int mid = (le + r) / 2;
		int f = bigs[mid];
		int y = v[f].S;
//		cout << "bs : " << mid << " " << y << endl;
		if(l[y] < l[v[x].S] * 2){
			le = mid;
		}else{
			r = mid;
		}
	}
	return r;
}

int main(){
	fast_io;
	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());
	
	fill(seg, seg + f * 4, 1);
	fill(c, c + f, 1);
	
	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 << t[x] << " : " << p << " " << c[t[x]] << " " << val << " " << p << " | " << in << " . " << ind[t[x]] << " " << ans << endl; 
		}
	}
	cout << ans % m;
	
	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: 0 / 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: 0 / 5