This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int F, K, M;
pair<int, int> fish[500005]; //(length, color)
struct mulseg
{
vector<int> tree;
mulseg(int n)
{
int sz = 1 << ((int)ceil(log2(n+1))+1);
tree.resize(sz);
}
int init(int s, int e, int node, vector<int> &arr)
{
if (s == e) return tree[node] = arr[s] % M;
return tree[node] = init(s, (s+e)/2, 2*node, arr) * init((s+e)/2+1, e, 2*node+1, arr) % M;
}
void upd(int s, int e, int node, int id, int diff)
{
if (e < id || id < s) return;
if (s == e) {
tree[node] = (tree[node] + diff + M) % M;
return;
}
upd(s, (s+e)/2, 2*node, id, diff);
upd((s+e)/2+1, e, 2*node+1, id, diff);
tree[node] = tree[2*node] * tree[2*node+1] % M;
}
int query(int s, int e, int node, int l, int r)
{
if (l > r) return 1;
if (e < l || r < s) return 1;
if (l <= s && e <= r) return tree[node];
return query(s, (s+e)/2, 2*node, l, r) * query((s+e)/2+1, e, 2*node+1, l, r) % M;
}
};
vector<int> lst[500005];
pair<int, int> x[500005];
signed main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin >> F >> K >> M;
for (int i = 0; i < F; i++) {
cin >> fish[i].first >> fish[i].second;
}
sort(fish, fish + F);
vector<int> trans(1, 0);
vector<bool> vis(K+1);
for (int i = F - 1; i >= 0; i--) {
if (!vis[fish[i].second]) {
trans.push_back(fish[i].second);
vis[fish[i].second] = true;
}
}
fill(x, x + 500005, make_pair(-1, -1));
vector<int> to(K+1);
for (int i = 1; i <= K; i++) to[trans[i]] = i;
for (int i = 0; i < F; i++) fish[i].second = to[fish[i].second];
for (int i = F-1; i >= 0; i--) {
if (x[fish[i].second].second == -1) {
x[fish[i].second] = make_pair(fish[i].first, i);
}
}
for (int i = 0; i < F; i++) lst[fish[i].second].push_back(fish[i].first);
mulseg seg(K);
vector<int> cnt(K+1);
int fin = fish[F-1].first;
int pos = 0;
while (pos < F && fish[pos].first <= fin/2) pos++;
for (int i = 0; i < pos; i++) cnt[fish[i].second]++;
for (int i = 1; i <= K; i++) cnt[i]++;
seg.init(1, K, 1, cnt);
int ans = 0;
for (int i = 1; i <= K; i++) {
int now = x[i].second;
while (pos > 0 && fish[pos-1].first > fish[now].first/2) {
seg.upd(1, K, 1, fish[pos-1].second, -1);
pos--;
}
int len = 2 * *upper_bound(lst[i].begin(), lst[i].end(), fish[now].first/2);
int l = 1, r = K;
while (l < r) {
int m = l + r >> 1;
if (x[m].first >= len) l = m+1;
else r = m;
}
ans += (seg.query(1, K, 1, l, i-1) - 1 + seg.query(1, K, 1, i, i)) * seg.query(1, K, 1, i+1, K);
ans %= M;
}
assert(0 <= ans && ans < M);
cout << ans << '\n';
}
Compilation message (stderr)
fish.cpp: In function 'int main()':
fish.cpp:84:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
84 | int m = l + r >> 1;
| ~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |