oj.uz

Submission #524735

# Submission time Handle Problem Language Result Execution time Memory
524735 2022-02-09T22:34:31 Z keta_tsimakuridze Fish (IOI08_fish) C++14
4 / 100
 391 ms 27772 KB 
#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5; // !
int tree[4 * N], mx[N], act[N], cnt[N], n, t, mod, f[N];
vector<int> occ[N];
pii p[N];
void upd(int u,int id, int l, int r, int val) {
	if(l > id || r < id) return;
	if(l == r) {
		tree[u] += val + mod;
		tree[u] %= mod;
		return;
	}
	int mid = (l + r) / 2;
	upd(2 * u, id, l, mid, val); upd(2 * u + 1, id, mid + 1, r, val);
	tree[u] = tree[2 * u] * tree[2 * u + 1] % mod;
}
int get(int u,int st,int en, int l,int r) {
	if(l > en || r < st) return 1;
	if(st <= l && r <= en) return tree[u];
	int mid = (l + r) / 2;
	return get(2 * u, st, en, l, mid) * get(2 * u + 1, st,en ,mid + 1, r) % mod;
}
int get(int c,int val) {
	int l = 0, r = occ[c].size(), P = -1; r--;
	while(l <= r) {
		int mid = (l + r) / 2;
		if(p[occ[c][mid]].f * 2 > val) r = mid - 1;
		else l = mid + 1, P = mid;
	}
	if(P == -1) return 0;
	return occ[c][P];
}
main(){
	cin >> n >> t >> mod;
	for(int i = 1; i <= t; i++) upd(1, i, 1 ,t, 1);
	for(int i = 1; i <= n; i++) {
		cin >> p[i].f >> p[i].s;
	}
	sort(p + 1, p + n + 1);
	for(int i = 1; i <= n; i++) {
		int c = p[i].s;
		mx[p[i].s] = max(mx[p[i].s], i);
	}
	for(int i = 1; i <= n; i++) {
		occ[p[i].s].push_back(i);
	}
	int L = 0, ans = 0, L1 = 0;
	for(int i =  1; i <= n; i++) {
		while(L1 < i && p[L1 + 1].f * 2 <= p[i].f) {
			L1++;
			int c = p[L1].s;
			if(act[c]) upd(1, c, 1, t, 1);
			cnt[c]++;			
		} 
		int c = p[i].s;

		while(L <= n - 1 && p[L + 1].f < 2 * p[i].f) {
			L++;
			if(L && mx[p[L].s] == L) act[p[L].s] = 1, upd(1, p[L].s ,1 ,t, cnt[p[L].s]);
		}
		if(!act[c] || occ[c].back() != i) continue;
		if(min(i, get(c, p[i].f)) == min(L, get(c, p[L].f))) {
			ans += get(1, 1, c - 1, 1, t) * get(1, c + 1, t, 1, t) % mod;
			ans %= mod;
			f[c] = 1;
		} 
	}
	
	for(int i = 1; i <= t; i++) upd(1, i ,1, t, -cnt[i]), cnt[i] = 0, act[i] = 0;
	L1 = 0;
	for(int i = 1; i <= t; i++) reverse(occ[i].begin(), occ[i].end());
	for(int i = 1; i <= n; i++) {
		if(mx[p[i].s] == i) act[p[i].s] = 1, upd(1, p[i].s, 1, t, cnt[p[i].s]);
		while(L1 < i && p[L1 + 1].f * 2 <= p[i].f) {
			L1++;
			int c = p[L1].s;
			if(act[c]) upd(1, c, 1, t, 1);
			cnt[c]++;			
		}
		int c = p[i].s;
		if(!act[c]) continue;
		ans += get(1, 1, c - 1, 1, t) * get(1, c + 1, t, 1, t) % mod * (cnt[c] - f[c] + 1) % mod;
		ans %= mod;
		
	}
	cout << ans;
}

Compilation message

fish.cpp:38:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   38 | main(){
      | ^~~~
fish.cpp: In function 'int main()':
fish.cpp:46:7: warning: unused variable 'c' [-Wunused-variable]
   46 |   int c = p[i].s;
      |       ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct

Subtask #2
0 / 4.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

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

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Runtime error 289 ms 16288 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

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

Subtask #8
0 / 6.0

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

Subtask #9
0 / 6.0

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

Subtask #10
0 / 6.0

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

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 195 ms 16356 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 287 ms 16324 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 220 ms 16388 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 344 ms 16948 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 336 ms 17536 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 298 ms 19112 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 357 ms 26928 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 298 ms 27008 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 391 ms 27772 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -