Submission #958799

#TimeUsernameProblemLanguageResultExecution timeMemory
958799relexBoat (APIO16_boat)C++17
9 / 100
2 ms476 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; using ll = long long; using ld = long double; struct custom_hash { static uint64_t splitmix64(uint64_t x) { // http://xorshift.di.unimi.it/splitmix64.c x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; gp_hash_table<ll, ll, custom_hash> app; //constexpr ll MOD = 998244353; constexpr ll MOD = 1e9 + 7; constexpr ll INF = 3e18; ll n, m, k, q, x, y, z, w, h, T; string s, t; double p; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); ll n; cin >> n; pair<ll, ll> a[n]; set<ll> s; for (ll i = 0; i < n; i++) { cin >> a[i].first >> a[i].second; s.insert(a[i].first); s.insert(a[i].second); } map<ll, ll> app; ll diff[2 * n + 10] = {}; ll pr = 0; ll cur = 1; for (ll val : s) { app[val] = cur; diff[cur] = val - pr; pr = val; cur++; } for (ll i = 0; i < n; i++) { a[i].first = app[a[i].first]; a[i].second = app[a[i].second]; } ll pref[cur] = {}; fill(pref, pref + cur, 1); for (ll i = 0; i < n; i++) { ll dp[cur] = {}; dp[a[i].first] = pref[a[i].first - 1]; for (ll j = a[i].first + 1; j <= a[i].second; j++) { dp[j] = (pref[j - 1] * diff[j]) % MOD; } ll ad = 0; for (ll j = 1; j < cur; j++) { ad += dp[j]; if (ad >= MOD) ad -= MOD; pref[j] += ad; if (pref[j] >= MOD) pref[j] -= MOD; } } ll ans = (pref[cur - 1] - 1 + MOD) % MOD; printf("%lld\n", ans); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...