# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
778384 |
2023-07-10T09:02:15 Z |
loctildore |
Fish (IOI08_fish) |
C++14 |
|
1030 ms |
63744 KB |
#include <bits/stdc++.h>
using namespace std;
// trans rights
#define int long long
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x), end(x)
int f, k, MOD;
struct node{
int l, r;
node *lft, *rht;
int val;
node(int tl, int tr): l(tl), r(tr), val(1) {
if (l + 1 == r) {
lft = rht = NULL;
return;
}
lft = new node(l, (l + r) / 2);
rht = new node((l + r) / 2, r);
}
void upd(int x, int tval) {
if (x < l || x >= r) return;
if (l + 1 == r) {
val = tval % MOD;
return;
}
lft->upd(x, tval);
rht->upd(x, tval);
val = (lft->val * rht->val) % MOD;
}
} *root1, *root2;
int cnt[500069], ans;
bool done[500069], lwrd[500069];
priority_queue<pair<int,int>> pq, tp;
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
//freopen("fish.in", "r", stdin);
//freopen("fish.out", "w", stdout);
cin>>f>>k>>MOD;
root1 = new node(0, k);
root2 = new node(0, k);
for (int i = 0; i < f; i++) {
int a, b;
cin>>a>>b; b--;
cnt[b]++;
pq.push({a, b});
tp.push({a, b});
}
for (int i = 0; i < k; i++) {
root1->upd(i, cnt[i] + 1);
root2->upd(i, cnt[i] + 1);
}
bool frst = true;
while (tp.size()) {
auto t = tp.top(); tp.pop();
if (done[t.s]) continue;
while(pq.size()) {
auto t2 = pq.top();
if (t2.f * 2 <= t.f) break;
pq.pop();
int i = t2.s;
cnt[i]--;
root1->upd(i, cnt[i] + 1);
if (!frst) lwrd[i] = true;
if (!done[i]) root2->upd(i, cnt[i] + 1);
}
int i = t.s;
if (frst) {
ans = (ans + root1->val) % MOD;
root2->upd(i, 1);
done[i] = true;
frst = false;
//cout<<ans<<endl;
continue;
}
if (lwrd[i]) {
ans = (ans + root2->val) % MOD;
}
else {
root1->upd(i, 1);
ans = (ans + root1->val) % MOD;
root1->upd(i, cnt[i] + 1);
root2->upd(i, cnt[i]);
ans = (ans + root2->val) % MOD;
}
root2->upd(i, 1);
done[i] = true;
//cout<<ans<<endl;
}
cout<<ans<<endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
328 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Incorrect |
216 ms |
22252 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
576 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
110 ms |
9164 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
928 KB |
Output is correct |
2 |
Incorrect |
5 ms |
928 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
158 ms |
16864 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
264 ms |
22684 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
192 ms |
17564 KB |
Output is correct |
2 |
Incorrect |
306 ms |
24488 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
330 ms |
23340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
396 ms |
26928 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
343 ms |
29036 KB |
Output is correct |
2 |
Correct |
926 ms |
43536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
940 ms |
51392 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
625 ms |
49492 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1030 ms |
63744 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |