Submission #1320869

#TimeUsernameProblemLanguageResultExecution timeMemory
1320869aaaaaaaaTrains (BOI24_trains)C++20
0 / 100
11 ms1940 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define all(x) x.begin(), x.end() const int mod = 1e9 + 7; int add(int x, int y){ return ((x % mod) + (y % mod)) % mod; } void testCase() { int n; cin >> n; vector<pair<int, int>> v(n + 1); vector<int> seg(n * 2, 0); for(int i = 1; i <= n; ++i){ cin >> v[i].first >> v[i].second; } auto update = [&](int idx, int v) -> void { idx += n - 1; seg[idx] = add(v, seg[idx]); while(idx > 1){ idx >>= 1; seg[idx] = add(seg[idx << 1], seg[idx << 1 | 1]); } }; auto query = [&](int l, int r) -> int { if(l > r) return 0; int ans = 0; l += n - 1, r += n - 1; while(l <= r){ if(l & 1) ans = add(ans, seg[l ++]); if(r & 1 ^ 1) ans = add(ans, seg[r --]); l >>= 1, r >>= 1; } return add(ans, mod); }; for(int i = 1; i <= n; ++i) update(i, 1); for(int i = n - 1; i >= 1; --i){ update(i, query(i + 1, i + v[i].second)); } cout << add(query(1, 1), mod) << "\n"; } signed main(){ ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); testCase(); 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...