#include "bits/stdc++.h"
using namespace std;
struct fish {
int l;
int g;
bool operator<(const fish& oth) {
return l < oth.l;
}
};
struct Segtree {
int n;
int m;
vector<int> t;
Segtree(int n, int m) : n(n), m(m), t(2*n, 1) {}
void inc(int p) {
t[p + n] %= m;
for (t[p += n] += 1; p > 1; p >>= 1) {
t[p >> 1] = t[p] * t[p ^ 1] % m;
}
}
int query(int l, int r) {
int ans = 1;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) ans = ans * t[l++] % m;
if (r & 1) ans = ans * t[--r] % m;
}
return ans;
}
};
signed main() {
int n; cin >> n;
int k; cin >> k;
int m; cin >> m;
vector<fish> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i].l >> a[i].g; --a[i].g;
}
sort(begin(a), end(a));
vector<int> last(k);
vector<vector<int>> o(k);
for (int i = 0; i < n; ++i) {
o[a[i].g].emplace_back(a[i].l);
last[a[i].g] = i;
}
vector<int> cs;
vector<int> idx(k);
for (int i = 0; i < n; ++i) {
if (last[a[i].g] == i) {
idx[a[i].g] = cs.size();
cs.push_back(a[i].g);
}
}
Segtree st(k, m);
int ans = 0;
vector<int> frq(k);
for (int r = 0, l = 0; r < n; ++r) {
int c = a[r].g;
if (last[c] != r) continue;
while (2*a[l].l <= a[r].l) {
st.inc(idx[a[l].g]);
++frq[a[l].g];
++l;
}
int cur1 = st.query(0, idx[c]) * (frq[c] % m) % m;
int ll = idx[c], rr = k;
while (rr - ll > 1) {
int mm = (ll + rr) / 2;
if (o[cs[mm]].back() < 2 * o[c][frq[c]]) {
ll = mm;
} else {
rr = mm;
}
}
int cur2 = st.query(0, idx[c]) * st.query(idx[c]+1, ll+1) % m;
ans = (ans + cur1 + cur2) % m;
}
cout << ans << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
347 ms |
6772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
145 ms |
3132 KB |
Output is correct |
2 |
Correct |
163 ms |
3604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
6 ms |
340 KB |
Output is correct |
3 |
Correct |
4 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
215 ms |
4684 KB |
Output is correct |
2 |
Correct |
385 ms |
6720 KB |
Output is correct |
3 |
Correct |
354 ms |
7004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
312 ms |
7416 KB |
Output is correct |
2 |
Correct |
359 ms |
7492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
225 ms |
4684 KB |
Output is correct |
2 |
Correct |
384 ms |
7256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
354 ms |
7272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
418 ms |
8556 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
322 ms |
8644 KB |
Output is correct |
2 |
Correct |
498 ms |
13800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
658 ms |
16256 KB |
Output is correct |
2 |
Correct |
431 ms |
14660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
454 ms |
17020 KB |
Output is correct |
2 |
Correct |
638 ms |
13808 KB |
Output is correct |
3 |
Correct |
533 ms |
21288 KB |
Output is correct |
4 |
Correct |
546 ms |
13848 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
870 ms |
20204 KB |
Output is correct |
2 |
Correct |
778 ms |
44268 KB |
Output is correct |
3 |
Correct |
749 ms |
45412 KB |
Output is correct |
4 |
Correct |
942 ms |
35868 KB |
Output is correct |