This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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];
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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |