Submission #947267

#TimeUsernameProblemLanguageResultExecution timeMemory
947267NValchanovBoat (APIO16_boat)C++17
9 / 100
400 ms524288 KiB
#include<bits/stdc++.h> #define endl '\n' #define a first #define b second using namespace std; typedef long long ll; const int MAXN = 512; const int MAXA = 1e6 + 10; const int MOD = 1e9 + 7; int n,cnt; pair<int,int> s[MAXN]; int dp[MAXN]; int pref[MAXN]; unordered_map <int,int> 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 <int> v; for(int i = 1; i <= n; i++) { int from = s[i].a; int to = s[i].b; for(int j = from; j <= to; j++) { v.push_back(j); } } sort(v.begin(), v.end()); int last = -1; for(int cur : v) { 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++) { int from = pos[s[i].a]; int 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...