#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;
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 |
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 |
16076 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
16076 KB |
Output is correct |
2 |
Correct |
11 ms |
16076 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
16192 KB |
Output is correct |
2 |
Correct |
209 ms |
22636 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
16204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
16236 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
82 ms |
19004 KB |
Output is correct |
2 |
Correct |
117 ms |
19636 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
16204 KB |
Output is correct |
2 |
Correct |
13 ms |
16272 KB |
Output is correct |
3 |
Correct |
13 ms |
16204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
139 ms |
20508 KB |
Output is correct |
2 |
Correct |
241 ms |
22528 KB |
Output is correct |
3 |
Correct |
237 ms |
22996 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
201 ms |
23236 KB |
Output is correct |
2 |
Correct |
229 ms |
23240 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
136 ms |
20828 KB |
Output is correct |
2 |
Correct |
230 ms |
22928 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
230 ms |
22724 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
241 ms |
23748 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
245 ms |
22736 KB |
Output is correct |
2 |
Correct |
337 ms |
26232 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
378 ms |
27204 KB |
Output is correct |
2 |
Correct |
330 ms |
25948 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
325 ms |
28324 KB |
Output is correct |
2 |
Correct |
373 ms |
26604 KB |
Output is correct |
3 |
Incorrect |
438 ms |
30772 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
549 ms |
29692 KB |
Output is correct |
2 |
Correct |
596 ms |
43528 KB |
Output is correct |
3 |
Correct |
635 ms |
41540 KB |
Output is correct |
4 |
Correct |
664 ms |
38972 KB |
Output is correct |