oj.uz

Submission #754029

# Submission time Handle Problem Language Result Execution time Memory
754029 2023-06-06T13:31:46 Z PoPularPlusPlus Fish (IOI08_fish) C++17
0 / 100
 541 ms 43628 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 168 ms 17876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 260 ms 29580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 457 ms 38224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 277 ms 31028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 411 ms 39468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 443 ms 42944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 340 ms 33544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 460 ms 39692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 393 ms 35044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 541 ms 43628 KB Output isn't correct
2 Halted 0 ms 0 KB -