#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<bool> is_long(f, false);
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)
{
is_long[i] = true;
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 (is_long[i])
{
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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4300 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4300 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4304 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4300 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
4428 KB |
Output is correct |
2 |
Correct |
3 ms |
4428 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
4428 KB |
Output is correct |
2 |
Correct |
206 ms |
10972 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4428 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
4428 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
87 ms |
7468 KB |
Output is correct |
2 |
Correct |
119 ms |
11188 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
4556 KB |
Output is correct |
2 |
Correct |
5 ms |
4556 KB |
Output is correct |
3 |
Correct |
5 ms |
4556 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
143 ms |
8780 KB |
Output is correct |
2 |
Correct |
254 ms |
10904 KB |
Output is correct |
3 |
Correct |
223 ms |
11316 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
229 ms |
11244 KB |
Output is correct |
2 |
Correct |
227 ms |
18532 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
127 ms |
8852 KB |
Output is correct |
2 |
Correct |
231 ms |
11384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
214 ms |
11468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
242 ms |
12436 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
200 ms |
13044 KB |
Output is correct |
2 |
Correct |
259 ms |
16964 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
362 ms |
19052 KB |
Output is correct |
2 |
Correct |
250 ms |
21552 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
290 ms |
19316 KB |
Output is correct |
2 |
Correct |
330 ms |
24876 KB |
Output is correct |
3 |
Correct |
319 ms |
29744 KB |
Output is correct |
4 |
Correct |
380 ms |
24760 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
444 ms |
22412 KB |
Output is correct |
2 |
Correct |
440 ms |
46916 KB |
Output is correct |
3 |
Correct |
380 ms |
47912 KB |
Output is correct |
4 |
Correct |
491 ms |
41740 KB |
Output is correct |