Submission #524728

#	Time	Username	Problem	Language	Result	Execution time	Memory
524728		keta_tsimakuridze	Fish (IOI08_fish)	C++14	0 / 100	399 ms	35668 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 = 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;
	p[n + 1] = p[n];
	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 && p[L + 1].f < 2 * p[i].f) {
			if(L && mx[p[L].s] == L) act[p[L].s] = 1, upd(1, p[L].s ,1 ,t, cnt[p[L].s]);
			L++;
		}
		if(!act[c]) 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;
		occ[c].pop_back();
		if(!act[c]) continue;
		if(!occ[c].size() || p[occ[c].back()].f < 2 * p[i].f) {
			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 (stderr)

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