oj.uz

Submission #364927

# Submission time Handle Problem Language Result Execution time Memory
364927 2021-02-10T13:09:00 Z minoum Fish (IOI08_fish) C++17
100 / 100
 946 ms 37996 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;

const int MAXN = 5e5+2;
int n, k, last[MAXN], lc[MAXN], nxt[MAXN], ff[MAXN];
ll md, seg[MAXN*4], ans = 0;
pair<int,int> f[MAXN], all[MAXN];

void add(int x, int b = 0, int e = k, int ind = 1){
	if(b+1 == e){
		seg[ind] = (seg[ind]+1)%md;
		return;
	}
	int mid = (b + e) / 2;
	if(x < mid) add(x, b, mid, ind * 2);
	else add(x, mid, e, ind * 2 + 1);
	seg[ind] = (seg[ind*2]*seg[ind*2+1])%md;
	return;
}

ll get(int l, int r, int b = 0, int e = k, int ind = 1){
	if(r <= b || e <= l) return 1ll; 
	if(l <= b && r >= e) return seg[ind];
	int mid = (b + e) / 2; ll res = 1ll;
	res = (res*get(l, r, b, mid, ind * 2))%md;
	res = (res*get(l, r, mid, e, ind * 2 + 1))%md;
	return res;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	for(int i = 0; i < MAXN*4; i++) seg[i] = 1ll;
	cin >> n >> k >> md;
	for(int i = 0; i < n; i++){
		cin >> f[i].first >> f[i].second; f[i].second--;
		all[f[i].second].second = f[i].second, all[f[i].second].first = max(all[f[i].second].first,f[i].first); 
	}
	sort(f,f+n);
	sort(all,all+k);
	for(int i = 0; i < k; i++) last[all[i].second] = i, lc[i] = -1;
	for(int i = 0; i < n; i++){
		if(lc[f[i].second]!=-1) nxt[lc[f[i].second]] = i;
		else ff[f[i].second] = i;
		lc[f[i].second] = i;
	}
	for(int i = 0; i < k; i++) lc[i] = -1;
	int pt = 0;
	for(int i = 0; i < k; i++){
		int cl = all[i].second, l = all[i].first;
		while(pt<n && l>=2*f[pt].first){
			lc[f[pt].second] = pt;
			add(last[f[pt].second]); pt++;
		}
		ll mul1 = get(0,i), tr = get(i,i+1), mul2; tr--;
		int ii = (lc[cl]==-1?ff[cl]:nxt[lc[cl]]);
		pair<int,int> p = {2*f[ii].first,0};
		int ind = lower_bound(all,all+k,p)-all;
		mul2 = get(i+1,ind);
		ans = (ans+((mul1*tr)%md))%md; ans = (ans+((mul1*mul2)%md))%md;
	}
	cout << ans << endl;
	return 0; 
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15980 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15980 KB Output is correct

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16108 KB Output is correct
2 Correct 174 ms 28012 KB Output is correct

Subtask #7
6.0 / 6.0

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

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16148 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 18412 KB Output is correct
2 Correct 104 ms 22272 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16108 KB Output is correct
2 Correct 13 ms 16108 KB Output is correct
3 Correct 13 ms 16236 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 19588 KB Output is correct
2 Correct 231 ms 28672 KB Output is correct
3 Correct 221 ms 28652 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 21996 KB Output is correct
2 Correct 228 ms 29164 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 19712 KB Output is correct
2 Correct 230 ms 29140 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 21612 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 22252 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 21484 KB Output is correct
2 Correct 288 ms 31596 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 514 ms 24492 KB Output is correct
2 Correct 398 ms 27372 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 24044 KB Output is correct
2 Correct 433 ms 31884 KB Output is correct
3 Correct 543 ms 32236 KB Output is correct
4 Correct 436 ms 31724 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 660 ms 25808 KB Output is correct
2 Correct 946 ms 37068 KB Output is correct
3 Correct 760 ms 37996 KB Output is correct
4 Correct 920 ms 37900 KB Output is correct