oj.uz

Submission #53867

# Submission time Handle Problem Language Result Execution time Memory
53867 2018-07-01T12:56:58 Z baactree Fish (IOI08_fish) C++17
100 / 100
 1472 ms 42628 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll tree[1 << 20];
int sz = 1 << 19;
int n, m, mod;
pair<int, int> arr[500005];
vector<int> vec[500005];
bool chk[500005];
int t[500005];
void update(int idx, int val) {
	idx += sz;
	tree[idx] += val;
	idx /= 2;
	while (idx) {
		tree[idx] = tree[idx * 2] * tree[idx * 2 + 1] % mod;
		idx /= 2;
	}
}
ll query(int le, int ri) {
	le += sz;
	ri += sz;
	ll ret = 1;
	while (le <= ri) {
		if (le & 1)ret = ret * tree[le++] % mod;
		if (!(ri & 1))ret = ret * tree[ri--] % mod;
		le /= 2;
		ri /= 2;
	}
	return ret;
}
int main() {
	scanf("%d%d%d", &n, &m, &mod);
	for (int i = 0; i < n; i++)
		scanf("%d%d", &arr[i].first, &arr[i].second);
	sort(arr, arr + n);
	int cnt = 0;
	for (int i = n - 1; i >= 0; i--) {
		if (!chk[arr[i].second]) {
			t[arr[i].second] = ++cnt;
			chk[arr[i].second] = true;
		}
	}
	for (int i = 0; i < n; i++) {
		arr[i].second = t[arr[i].second];
		vec[arr[i].second].push_back(i);
	}
	ll ans = 0;
	for (int i = 0; i < 500005; i++)
		tree[i + sz] = 1;
	for (int i = sz - 1; i; i--)
		tree[i] = tree[i * 2] * tree[i * 2 + 1] % mod;
	int idx = 0;
	for (int i = 0; i < n; i++) {
		while (arr[idx].first * 2 <= arr[i].first) {
			update(arr[idx].second, 1);
			idx++;
		}
		if (vec[arr[i].second].back()==i) {
			update(arr[i].second, -1);
			ans = (ans + query(arr[i].second, 500004)) % mod;
			int it = -1;
			for (auto x : vec[arr[i].second]) {
				if (arr[x].first > arr[i].first / 2) {
					it = x;
					break;
				}
			}
			int le = arr[it].first * 2;
			int l, r, mid, ri;
			l = 1;
			r = arr[i].second;
			while (l <= r) {
				mid = (l + r) / 2;
				if (arr[vec[mid].back()].first < le) {
					ri = mid;
					r = mid - 1;
				}
				else l = mid + 1;
			}
			ans = (ans + query(ri, arr[i].second - 1) * query(arr[i].second + 1, 500004)) % mod;
			update(arr[i].second, 1);
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

fish.cpp: In function 'int main()':
fish.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &mod);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &arr[i].first, &arr[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:81:22: warning: 'ri' may be used uninitialized in this function [-Wmaybe-uninitialized]
    ans = (ans + query(ri, arr[i].second - 1) * query(arr[i].second + 1, 500004)) % mod;
                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 20088 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 20196 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 20276 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 20324 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 20356 KB Output is correct
2 Correct 27 ms 20356 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 20356 KB Output is correct
2 Correct 420 ms 26764 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 26764 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 26764 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 26764 KB Output is correct
2 Correct 206 ms 26764 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 26764 KB Output is correct
2 Correct 31 ms 26764 KB Output is correct
3 Correct 31 ms 26764 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 26764 KB Output is correct
2 Correct 440 ms 26812 KB Output is correct
3 Correct 408 ms 26812 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 26988 KB Output is correct
2 Correct 347 ms 27500 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 27500 KB Output is correct
2 Correct 413 ms 27500 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 27500 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 27780 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 27780 KB Output is correct
2 Correct 615 ms 29564 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 930 ms 29948 KB Output is correct
2 Correct 733 ms 29948 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 738 ms 30848 KB Output is correct
2 Correct 1034 ms 30848 KB Output is correct
3 Correct 877 ms 32784 KB Output is correct
4 Correct 796 ms 32784 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1234 ms 32784 KB Output is correct
2 Correct 1472 ms 42628 KB Output is correct
3 Correct 1316 ms 42628 KB Output is correct
4 Correct 1448 ms 42628 KB Output is correct