| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1108610 |
2024-11-04T15:22:43 Z |
kyaruru |
Fish (IOI08_fish) |
C++17 |
|
69 ms |
65536 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
int a, b, c;
cin >> a >> b >> c;
pll k[a + 1];
for (int i = 1; i <= a; i++) {
ll x, y;
cin >> x >> y;
k[i] = {x, y};
}
int h = ceil(log2(b));
int n = (1 << h) - 1;
vector<ll> seg(1 << (h + 1), 1), sega(1 << (h + 1), 1);
sort(k + 1, k + a + 1);
ll ed[b + 1], sv[b + 1], u[b + 1];
memset(ed, -1, sizeof(ed));
memset(u, -1, sizeof(u));
memset(sv, 0, sizeof(sv));
int m = b;
for (int i = a; i >= 1; i--) {
if (ed[k[i].second] == -1) ed[k[i].second] = m--;
k[i].second = ed[k[i].second];
}
vector<int> ka;
memset(ed, -1, sizeof(ed));
for (int i = a; i >= 1; i--) {
if (ed[k[i].second] == -1)
ed[k[i].second] = i, ka.push_back(k[i].first);
else if (2 * k[i].first > k[ed[k[i].second]].first)
u[k[i].second] = k[i].first;
}
sort(ka.begin(), ka.end());
ll r = 1, ans = 0;
for (int i = 1; i <= a; i++) {
while (2 * k[r].first <= k[i].first) {
if (ed[k[r].second] < i) {
int j = k[r].second + n;
seg[j]++;
for (j /= 2; j >= 1; j /= 2) seg[j] = seg[2 * j] * seg[2 * j + 1] % c;
} else
sv[k[r].second]++;
int j = k[r].second + n;
sega[j]++;
for (j /= 2; j >= 1; j /= 2) sega[j] = sega[2 * j] * sega[2 * j + 1] % c;
r++;
}
if (ed[k[i].second] == i) {
int j = k[i].second + n;
seg[j] += sv[k[i].second];
for (j /= 2; j >= 1; j /= 2) seg[j] = seg[2 * j] * seg[2 * j + 1] % c;
ans += seg[1];
j = k[i].second + n;
ll p = sega[j];
sega[j] = seg[j] = 1;
for (j /= 2; j >= 1; j /= 2) {
sega[j] = sega[2 * j] * sega[2 * j + 1] % c;
seg[j] = seg[2 * j] * seg[2 * j + 1] % c;
}
int v = u[k[i].second] == -1 ? b : lower_bound(ka.begin(), ka.end(), 2 * u[k[i].second]) - ka.begin();
ll l = 1 + n, r = v + n, t = 1, tt = 1;
while (l <= r) {
if (l % 2 == 1) {
t = t * sega[l] % c;
tt = tt * seg[l] % c;
l++;
}
if (r % 2 == 0) {
t = t * sega[r] % c;
tt = tt * seg[r] % c;
r--;
}
l /= 2, r /= 2;
}
ans += t - tt;
j = k[i].second + n;
sega[j] = seg[j] = p;
for (j /= 2; j >= 1; j /= 2) {
sega[j] = sega[2 * j] * sega[2 * j + 1] % c;
seg[j] = seg[2 * j] * seg[2 * j + 1] % c;
}
}
}
cout << (ans % c + c) % c;
}
Compilation message
fish.cpp: In function 'int main()':
fish.cpp:11:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
11 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | freopen("output.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
58 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
59 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
69 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
61 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
58 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
69 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
61 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
65 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
62 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
59 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
66 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
63 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
64 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
62 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
65 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
55 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
62 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
60 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
59 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
