Submission #947264

#TimeUsernameProblemLanguageResultExecution timeMemory
947264NValchanovBoat (APIO16_boat)C++17
9 / 100
286 ms524288 KiB
#include<bits/stdc++.h> #define endl '\n' #define a first #define b second using namespace std; typedef long long ll; const ll MAXN = 512; const ll MAXA = 1e6 + 10; const ll MOD = 1e9 + 7; ll n,cnt; pair<ll,ll> s[MAXN]; ll dp[MAXN]; ll pref[MAXN]; unordered_map <ll,ll> pos; void read() { cin >> n; for(int i = 1; i <= n; i++) { cin >> s[i].a >> s[i].b; } s[0].a = s[0].b = 0; } void fill_pos() { vector <ll> v; for(int i = 1; i <= n; i++) { for(int j = s[i].a; j <= s[i].b; j++) { v.push_back(j); } } sort(v.begin(), v.end()); ll last = -1; ll sz = v.size(); for(int i = 0; i < sz; i++) { ll cur = v[i]; if(cur == last) continue; pos[cur] = ++cnt; last = cur; } /** for(auto x : pos) { cout << x.first << " " << x.second << endl; } */ } void fill_dp() { for(int i = 1; i <= n; i++) { ll from = pos[s[i].a]; ll to = pos[s[i].b]; for(int j = to; j >= from; j--) { dp[j] = (dp[j] + pref[j - 1] + 1 /** za nulata **/) % MOD; } for(int j = from; j <= cnt; j++) { pref[j] = (pref[j - 1] + dp[j]) % MOD; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); read(); fill_pos(); fill_dp(); cout << pref[cnt] << 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...