oj.uz

Submission #524728

# Submission time Handle Problem Language Result Execution time Memory
524728 2022-02-09T22:04:50 Z keta_tsimakuridze Fish (IOI08_fish) C++14
0 / 100
 399 ms 35668 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;
	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

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.0

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

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4992 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 3 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 Incorrect 3 ms 5068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5016 KB Output is correct
2 Runtime error 395 ms 22320 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 6 ms 5196 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 159 ms 13200 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 5240 KB Output is correct
2 Correct 9 ms 5352 KB Output is correct
3 Incorrect 9 ms 5196 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 233 ms 20428 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 325 ms 22476 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 231 ms 20716 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 292 ms 23312 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 333 ms 25020 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 296 ms 25344 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 348 ms 34068 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 307 ms 32068 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 399 ms 35668 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -