Submission #778596

#TimeUsernameProblemLanguageResultExecution timeMemory
778596loctildoreFish (IOI08_fish)C++14
95 / 100
713 ms65536 KiB
#include <bits/stdc++.h> using namespace std; // trans rights #define ll 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; } int fnd(int tl, int tr) { if (tr <= l || r <= tl) return 1; if (tl <= l && r <= tr) return val; return (lft->fnd(tl, tr) * rht->fnd(tl, tr)) % MOD; } } *root; int ans; int maxi[500069], loc[500069]; int chng[500069]; int cnt[500069]; vector<int> vals[500069]; priority_queue<pair<int,int>> pq; vector<pair<int,int>> ord; 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; root = new node(0, k); for (int i = 0; i < f; i++) { int a, b; cin>>a>>b; b--; maxi[b] = max(maxi[b], a); vals[b].push_back(a); pq.push({a, b}); } for (int i = 0; i < k; i++) { ord.push_back({maxi[i], i}); } sort(all(ord)); for (int i = 0; i < k; i++) loc[ord[i].s] = i; for (int i = 0; i < k; i++) { sort(all(vals[i])); int t = *upper_bound(all(vals[i]), *vals[i].rbegin() / 2); chng[loc[i]] = lower_bound(all(ord), make_pair(t * 2, INT_MIN)) - begin(ord); cnt[loc[i]] = vals[i].size(); root->upd(loc[i], cnt[loc[i]] + 1); } for (int i = k - 1; ~i; i--) { while (pq.size()) { auto t = pq.top(); if (t.f * 2 <= ord[i].f) break; pq.pop(); int pos = loc[t.s]; cnt[pos]--; root->upd(pos, cnt[pos] + 1); } root->upd(i, 1); ans = (ans + root->fnd(0, chng[i])) % MOD; root->upd(i, cnt[i]); ans = (ans + root->fnd(0, i + 1)) % MOD; root->upd(i, cnt[i] + 1); } cout<<ans<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...