Submission #1011953

#TimeUsernameProblemLanguageResultExecution timeMemory
1011953thinknoexitFish (IOI08_fish)C++17
0 / 100
174 ms19652 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 500500; int MOD, n; pair<int, int> a[N]; int tree[4 * N], cnt[N]; bool ch[N]; int mx[N]; void build(int now = 1, int l = 1, int r = n) { tree[now] = 1; if (l == r) return; int mid = (l + r) / 2; build(2 * now, l, mid), build(2 * now + 1, mid + 1, r); } void update(int v, int w, int now = 1, int l = 1, int r = n) { if (l == r) { tree[now] = (tree[now] + w + MOD) % MOD; return; } int mid = (l + r) / 2; if (v <= mid) update(v, w, 2 * now, l, mid); else update(v, w, 2 * now + 1, mid + 1, r); tree[now] = tree[2 * now] * tree[2 * now + 1] % MOD; } int query(int ql, int qr, int now = 1, int l = 1, int r = n) { if (ql > qr) return 1; if (l > qr || r < ql) return 1; if (ql <= l && r <= qr) return tree[now]; int mid = (l + r) / 2; return query(ql, qr, 2 * now, l, mid) * query(ql, qr, 2 * now + 1, mid + 1, r) % MOD; } int main() { cin.tie(nullptr)->sync_with_stdio(false); int m; cin >> m >> n >> MOD; for (int i = 1;i <= m;i++) { cin >> a[i].first >> a[i].second; mx[a[i].second] = max(mx[a[i].second], a[i].first); } vector<pair<int, int>> v; for (int i = 1;i <= n;i++) { v.push_back({ mx[i], i }); } sort(v.begin(), v.end()); sort(a + 1, a + 1 + m); build(); int ans = 0; int p = 0; for (int i = 1;i <= n;i++) { int l, t; tie(l, t) = v[i - 1]; while (p < n && a[p + 1].first * 2 <= l) { p++; cnt[a[p].second]++; if (ch[a[p].second]) update(a[p].second, 1); } update(t, cnt[t]); ch[t] = 1; ans = (ans + tree[1]) % MOD; } cout << ans; 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...