#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int mxF = 5e5;
int f,k,m,cnt[mxF],ord[mxF],st[1<<20],ans;
vector<int> of_type[mxF];
void upd(int x, int v) {
st[x += k] = v%m;
for (; x/=2; ) st[x] = st[x*2]*st[x*2+1]%m;
}
int qry(int l, int r) {
int res = 1;
for (l += k, r += k; l < r; l/=2, r/=2) {
if (l&1) res=res*st[l++]%m;
if (r&1) res=res*st[--r]%m;
}
return res;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
fill(st, end(st), 1);
cin >> f >> k >> m;
vector<pii> fish(f);
for (int i = 0,l,x; i < f; ++i) {
cin >> l >> x;
x--;
of_type[x].push_back(l);
fish[i] = {l, x};
}
sort(fish.begin(), fish.end());
for (int x = 0; x < k; ++x) sort(of_type[x].begin(), of_type[x].end());
vector<pii> types(k);
for (int i = 0; i < k; ++i) {
types[i] = {of_type[i].back(), i};
}
sort(types.begin(), types.end());
for (int i = 0; i < k; ++i) ord[types[i].second] = i;
int smallest = 0;
for (auto [l,x]: types) {
while (fish[smallest].first <= l/2) {
cnt[fish[smallest].second]++;
upd(ord[fish[smallest].second], cnt[fish[smallest].second]+1);
smallest++;
}
int ltm = qry(0, ord[x]);
ans = (ans+(ltm*(cnt[x]%m)))%m;
int sm_of_type = *upper_bound(of_type[x].begin(), of_type[x].end(), l/2);
ans = (ans+(ltm*qry(ord[x]+1, lower_bound(types.begin(), types.end(), make_pair(2*sm_of_type,0))-types.begin())))%m;
}
cout << ans;
}
Compilation message
fish.cpp: In function 'int main()':
fish.cpp:44:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
44 | for (auto [l,x]: types) {
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
16164 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
16076 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
16076 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
16076 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
16136 KB |
Output is correct |
2 |
Correct |
11 ms |
16076 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
16084 KB |
Output is correct |
2 |
Correct |
209 ms |
22500 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
16076 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
16208 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
83 ms |
18960 KB |
Output is correct |
2 |
Correct |
126 ms |
19712 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
16292 KB |
Output is correct |
2 |
Correct |
13 ms |
16204 KB |
Output is correct |
3 |
Correct |
13 ms |
16248 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
135 ms |
20552 KB |
Output is correct |
2 |
Correct |
265 ms |
22588 KB |
Output is correct |
3 |
Correct |
235 ms |
22840 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
193 ms |
23264 KB |
Output is correct |
2 |
Correct |
225 ms |
23160 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
156 ms |
20672 KB |
Output is correct |
2 |
Correct |
250 ms |
22912 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
213 ms |
22716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
255 ms |
23832 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
213 ms |
22832 KB |
Output is correct |
2 |
Correct |
297 ms |
26084 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
402 ms |
27248 KB |
Output is correct |
2 |
Correct |
301 ms |
25936 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
332 ms |
28352 KB |
Output is correct |
2 |
Correct |
397 ms |
26512 KB |
Output is correct |
3 |
Correct |
413 ms |
30544 KB |
Output is correct |
4 |
Correct |
371 ms |
34284 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
590 ms |
29652 KB |
Output is correct |
2 |
Correct |
573 ms |
43464 KB |
Output is correct |
3 |
Correct |
609 ms |
41540 KB |
Output is correct |
4 |
Correct |
661 ms |
38844 KB |
Output is correct |