oj.uz

Submission #524867

# Submission time Handle Problem Language Result Execution time Memory
524867 2022-02-10T07:21:09 Z keta_tsimakuridze Fish (IOI08_fish) C++14
100 / 100
 1510 ms 63736 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 = 5e5 + 5; // !
int tree[4 * N], mx[N], act[N], cnt[N], n, t, mod, f[N], aft[N], last[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;
	}
	return P;
}
main(){
	cin >> n >> t >> mod;
	for(int i = 1; i <= n; i++) upd(1, i, 1 ,n, 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++) {
		if(mx[p[i].s] != i) continue;
		while(L1 < i && p[L1 + 1].f * 2 <= p[i].f) {
			L1++;
			int c = p[L1].s;
			upd(1, mx[c], 1, n, 1);
			cnt[c]++;			
		} 
		int c = p[i].s;
		int x = occ[c][cnt[c]];
		int l = i, r = n, pos = i;
		while(l <= r) {
			int mid = (l + r) / 2;
			if(p[x].f * 2 > p[mid].f) pos = mid, l = mid + 1;
			else r = mid - 1; 
		}
		ans += get(1, 1, i - 1, 1, n) * get(1, i + 1, pos, 1, n) % mod;
	}
	
	for(int i = 1; i <= t; i++) upd(1, mx[i] ,1, n, -cnt[i]), cnt[i] = 0, act[i] = 0;

	L1 = 0;
	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]) % mod;
		ans %= mod;
		
	}
	cout << ans;
}

Compilation message

fish.cpp:37:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   37 | main(){
      | ^~~~
fish.cpp: In function 'int main()':
fish.cpp:45:7: warning: unused variable 'c' [-Wunused-variable]
   45 |   int c = p[i].s;
      |       ^
fish.cpp:52:6: warning: unused variable 'L' [-Wunused-variable]
   52 |  int L = 0, ans = 0, L1 = 0;
      |      ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11980 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12056 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12056 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12072 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12108 KB Output is correct
2 Correct 7 ms 12108 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12060 KB Output is correct
2 Correct 524 ms 38716 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12108 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12236 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 24336 KB Output is correct
2 Correct 290 ms 26152 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12268 KB Output is correct
2 Correct 13 ms 12492 KB Output is correct
3 Correct 12 ms 12364 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 33068 KB Output is correct
2 Correct 552 ms 39488 KB Output is correct
3 Correct 523 ms 40372 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 39848 KB Output is correct
2 Correct 540 ms 41364 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 33232 KB Output is correct
2 Correct 559 ms 40620 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 39300 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 42308 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 37864 KB Output is correct
2 Correct 663 ms 45724 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 929 ms 45488 KB Output is correct
2 Correct 706 ms 38832 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 801 ms 44112 KB Output is correct
2 Correct 857 ms 45936 KB Output is correct
3 Correct 957 ms 48304 KB Output is correct
4 Correct 846 ms 45748 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1157 ms 48772 KB Output is correct
2 Correct 1389 ms 62688 KB Output is correct
3 Correct 1385 ms 63736 KB Output is correct
4 Correct 1510 ms 58500 KB Output is correct