# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
448612 |
2021-07-31T07:32:55 Z |
prvocislo |
Fish (IOI08_fish) |
C++17 |
|
460 ms |
30320 KB |
#include <iostream>
#include <vector>
#include <algorithm>
typedef long long ll;
using namespace std;
int f, k, m;
void add(int& a, const int& b) { a += b; if (a >= m) a -= m; }
int mul(const int& a, const int& b) { return (a * b) % m; }
const int maxn = 1 << 19, inf = 1e9 + 5;
//const int maxn = 4, inf = 1e9 + 5;
vector<int> st(maxn * 2, 1);
void upd(int i)
{
add(st[i += maxn], 1);
for (i = (i >> 1); i > 0; i >>= 1) st[i] = mul(st[i << 1], st[i << 1 | 1]);
}
int query(int l, int r)
{
int ans = 1;
for (l += maxn, r += maxn+1; l < r; l >>= 1, r >>= 1)
{
if (l & 1) ans = mul(ans, st[l++]);
if (r & 1) ans = mul(ans, st[--r]);
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> f >> k >> m;
vector<pair<int, int> > fish(f);
vector<int> longest(k, -1), order(k, -1);
vector<vector<int> > typ(k, vector<int>(1, inf));
for (int i = 0; i < f; i++) cin >> fish[i].first >> fish[i].second, fish[i].second--;
int num = k;
sort(fish.begin(), fish.end());
for (int i = f - 1; i >= 0; i--)
{
if (order[fish[i].second] == -1)
{
order[fish[i].second] = --num;
longest[num] = fish[i].first;
}
fish[i].second = order[fish[i].second];
typ[fish[i].second].push_back(fish[i].first);
}
int j = -1, ans = 0;
for (int i = 0; i < f; i++) if (longest[fish[i].second] == fish[i].first)
{
while (fish[j + 1].first * 2 <= fish[i].first)
upd(fish[++j].second), typ[fish[j].second].pop_back();
//cout << query(0, fish[i].second) << "\n";
add(ans, mul(query(0, fish[i].second-1), (m + st[maxn+fish[i].second] - 1) % m));
int r = lower_bound(longest.begin(), longest.end(), typ[fish[i].second].back() * 2) - longest.begin() - 1;
//cout << query(0, fish[i].second - 1) << "*" << query(fish[i].second + 1, r) << "\n";
add(ans, mul(query(0, fish[i].second - 1), query(fish[i].second + 1, r)));
}
cout << ans << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4428 KB |
Output is correct |
2 |
Correct |
3 ms |
4428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4428 KB |
Output is correct |
2 |
Correct |
220 ms |
16956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
89 ms |
9832 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4556 KB |
Output is correct |
2 |
Correct |
7 ms |
4556 KB |
Output is correct |
3 |
Correct |
5 ms |
4556 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
133 ms |
12876 KB |
Output is correct |
2 |
Correct |
247 ms |
17476 KB |
Output is correct |
3 |
Correct |
230 ms |
17956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
235 ms |
17272 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
132 ms |
13148 KB |
Output is correct |
2 |
Correct |
254 ms |
18348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
216 ms |
17672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
253 ms |
19792 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
204 ms |
19140 KB |
Output is correct |
2 |
Correct |
289 ms |
24740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
345 ms |
26040 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
295 ms |
24380 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
460 ms |
30320 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |