Submission #448618

#TimeUsernameProblemLanguageResultExecution timeMemory
448618prvocisloFish (IOI08_fish)C++17
4 / 100
416 ms37156 KiB
#include <iostream> #include <vector> #include <algorithm> typedef long long ll; using namespace std; int f, k, m; void add(int& a, const int& b) { a += b; if (a >= m) a -= m; } int mul(const int& a, const int& b) { return (a * b) % m; } //const int maxn = 1 << 19, inf = 1e9 + 5; const int maxn = 4, inf = 1e9 + 5; vector<int> st(maxn * 2, 1); void upd(int i) { add(st[i += maxn], 1); for (i = (i >> 1); i > 0; i >>= 1) st[i] = mul(st[i << 1], st[i << 1 | 1]); } int query(int l, int r) { int ans = 1; for (l += maxn, r += maxn+1; l < r; l >>= 1, r >>= 1) { if (l & 1) ans = mul(ans, st[l++]); if (r & 1) ans = mul(ans, st[--r]); } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> f >> k >> m; vector<pair<int, int> > fish(f); vector<int> longest(k, -1), order(k, -1); vector<bool> is_long(f, false); vector<vector<int> > typ(k, vector<int>(1, inf)); for (int i = 0; i < f; i++) cin >> fish[i].first >> fish[i].second, fish[i].second--; int num = k; sort(fish.begin(), fish.end()); for (int i = f - 1; i >= 0; i--) { if (order[fish[i].second] == -1) { is_long[i] = true; order[fish[i].second] = --num; longest[num] = fish[i].first; } fish[i].second = order[fish[i].second]; typ[fish[i].second].push_back(fish[i].first); } int j = -1, ans = 0; for (int i = 0; i < f; i++) if (is_long[i]) { while (fish[j + 1].first * 2 <= fish[i].first) upd(fish[++j].second), typ[fish[j].second].pop_back(); //cout << query(0, fish[i].second) << "\n"; add(ans, mul(query(0, fish[i].second-1), (m + st[maxn+fish[i].second] - 1) % m)); int r = lower_bound(longest.begin(), longest.end(), typ[fish[i].second].back() * 2) - longest.begin() - 1; //cout << query(0, fish[i].second - 1) << "*" << query(fish[i].second + 1, r) << "\n"; add(ans, mul(query(0, fish[i].second - 1), query(fish[i].second + 1, r))); } cout << ans << "\n"; 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...