Submission #754029

#	Time	Username	Problem	Language	Result	Execution time	Memory
754029		PoPularPlusPlus	Fish (IOI08_fish)	C++17	0 / 100	541 ms	43628 KiB

fish

#include <bits/stdc++.h>

using namespace std;
#define ll long long

int mod;

struct Seg {
	int siz;
	vector<ll> v;
	
	void init(int n){
		siz = 1;
		while(siz < n)siz *= 2;
		
		v.assign(siz * 2,1);
	}
	
	void set(int i , int val , int x , int lx , int rx){
		if(rx - lx == 1){
			v[x] = val;
			return;
		}
		int m = (lx + rx)/2;
		if(i < m)set(i ,val , 2 * x + 1 , lx , m);
		else set(i , val , 2 *x + 2 , m , rx);
		v[x] = (v[2*x+1]*v[2*x+2])%mod;
	}
	
	void set(int i , int val){
		set(i , val , 0 , 0 , siz);
	}
};

ll power(ll x , ll y){
	x %= mod;
	ll res = 1;
	while(y > 0){
		if(y&1)res = (res * x) % mod;
		x = x*x;
		x %= mod;
		y >>= 1;
	}
	return res;
}

int main(){
	int n;
	cin >> n;
	int gems;
	cin >> gems;
	cin >> mod;
	vector<pair<int,int>> arr(n);
	for(int i = 0; i < n; i++){
		cin >> arr[i].first >> arr[i].second;
	}
	sort(arr.begin(),arr.end());
	vector<int> cnt[n+1];
	ll res[n+1];
	memset(res,0,sizeof res);
	int done[n+1];
	ll ans = 0;
	memset(done,0,sizeof done);
	Seg st;
	st.init(n + 1);
	for(int i = 0; i < n; i++){
		if(done[arr[i].second] == 0){
			done[arr[i].second] = 1;
			ans++;
		}
		int pos = lower_bound(arr.begin(),arr.end(),make_pair(arr[i].first*2,-1)) - arr.begin();
		cnt[pos].push_back(arr[i].second);
		for(int j : cnt[i]){
			res[j]++;
			st.set(j , power(2,res[j]));
		}
		int x = st.v[0];
		if(x > 1)ans += x;
		ans %= mod;
	}
	cout << ans << '\n';
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6
• Subtask 10: 0 / 6
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 7
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5