# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|
1005429 | | gyg | Fish (IOI08_fish) | C++17 | | 961 ms | 30388 KiB |
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>
using namespace std;
using lint = long long;
using pii = pair<int, int>;
const int MAX_N = 5e5 + 5, MAX_K = 5e5 + 5;
int n, k;
lint m;
int len[MAX_N], a[MAX_N];
lint mod(lint x) { return (x + m) % m; }
lint st[4 * MAX_K];
void update(int i, lint x, int u = 1, int lo = 1, int hi = k) {
if (i < lo || hi < i) return;
if (lo == hi) { st[u] += x; return; }
int mid = (lo + hi) / 2;
update(i, x, 2 * u, lo, mid), update(i, x, 2 * u + 1, mid + 1, hi);
st[u] = mod(st[2 * u] * st[2 * u + 1]);
}
lint query(int l, int r, int u = 1, int lo = 1, int hi = k) {
if (l > r) return 1; // 0?
if (r < lo || hi < l) return 1;
if (l <= lo && hi <= r) return st[u];
int mid = (lo + hi) / 2;
return mod(query(l, r, 2 * u, lo, mid) * query(l, r, 2 * u + 1, mid + 1, hi));
}
void precomp() {
vector<pii> ord;
for (int i = 1; i <= n; i++) ord.push_back({len[i], a[i]});
sort(ord.rbegin(), ord.rend());
unordered_map<int, int> val;
for (pii x : ord) {
if (val.count(x.second)) continue;
val.insert({x.second, val.size() + 1});
}
for (int i = 1; i <= n; i++) {
len[i] = ord[i - 1].first, a[i] = val[ord[i - 1].second];
update(a[i], 1);
}
for (int i = 1; i <= k; i++) update(i, 1);
// for (int i = 1; i <= n; i++) {
// cout << len[i] << " " << a[i] << endl;
// }
// cout << endl;
// cout << query(1, 2) << endl;
}
lint comp() {
lint ans = 0;
unordered_map<int, int> max_freq;
int max_seen = 0;
int r = 1;
for (int l = 1; l <= n; l++) {
while (r != n + 1 && 2 * len[r] > len[l])
update(a[r], -1), r++;
update(a[l], 1);
lint new_ans = 0;
if (l == 1) {
assert(a[l] == 1);
new_ans = mod(query(2, k) * mod(query(1, 1) - 1));
max_seen = 1;
for (int i = 1; i <= k; i++) max_freq[i] = query(i, i);
} else {
bool cond1 = false, cond2 = false;
if (a[l] > max_seen)
cond1 = true, max_seen = a[l];
if (query(a[l], a[l]) > max_freq[a[l]])
cond2 = true, max_freq[a[l]] = query(a[l], a[l]);
if (cond2)
new_ans = mod(query(1, a[l] - 1) * query(a[l] + 1, k));
if (cond1) {
lint x = (cond2) ? mod(query(a[l], a[l]) - 2) : mod(query(a[l], a[l]) - 1);
new_ans = mod(new_ans + mod(query(a[l] + 1, k) * x));
}
}
// cout << l << ": " << new_ans << endl;
update(a[l], -1);
ans = mod(ans + new_ans);
}
return ans;
}
int main() {
// freopen("fish.in", "r", stdin), freopen("fish.out", "w", stdout);
cin >> n >> k >> m;
for (int i = 1; i <= n; i++) cin >> len[i] >> a[i];
precomp();
lint ans = comp();
cout << ans << '\n';
}
# | 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... |