Submission #364927

#	Time	Username	Problem	Language	Result	Execution time	Memory
364927		minoum	Fish (IOI08_fish)	C++17	100 / 100	946 ms	37996 KiB

fish

#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;

const int MAXN = 5e5+2;
int n, k, last[MAXN], lc[MAXN], nxt[MAXN], ff[MAXN];
ll md, seg[MAXN*4], ans = 0;
pair<int,int> f[MAXN], all[MAXN];

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

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

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	for(int i = 0; i < MAXN*4; i++) seg[i] = 1ll;
	cin >> n >> k >> md;
	for(int i = 0; i < n; i++){
		cin >> f[i].first >> f[i].second; f[i].second--;
		all[f[i].second].second = f[i].second, all[f[i].second].first = max(all[f[i].second].first,f[i].first); 
	}
	sort(f,f+n);
	sort(all,all+k);
	for(int i = 0; i < k; i++) last[all[i].second] = i, lc[i] = -1;
	for(int i = 0; i < n; i++){
		if(lc[f[i].second]!=-1) nxt[lc[f[i].second]] = i;
		else ff[f[i].second] = i;
		lc[f[i].second] = i;
	}
	for(int i = 0; i < k; i++) lc[i] = -1;
	int pt = 0;
	for(int i = 0; i < k; i++){
		int cl = all[i].second, l = all[i].first;
		while(pt<n && l>=2*f[pt].first){
			lc[f[pt].second] = pt;
			add(last[f[pt].second]); pt++;
		}
		ll mul1 = get(0,i), tr = get(i,i+1), mul2; tr--;
		int ii = (lc[cl]==-1?ff[cl]:nxt[lc[cl]]);
		pair<int,int> p = {2*f[ii].first,0};
		int ind = lower_bound(all,all+k,p)-all;
		mul2 = get(i+1,ind);
		ans = (ans+((mul1*tr)%md))%md; ans = (ans+((mul1*mul2)%md))%md;
	}
	cout << ans << 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