Submission #524867

#	Time	Username	Problem	Language	Result	Execution time	Memory
524867		keta_tsimakuridze	Fish (IOI08_fish)	C++14	100 / 100	1510 ms	63736 KiB

fish

#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 (stderr)

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 / 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