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>
using namespace std;
//#define FILE_IO
const int mod = 1e9 + 7;
int N, K;
int a[1005], b[1005], st[1005], dr[1005];
int dp[1005][4005], sum[1005][4005]; /// primele i, ultimul este in intervalul j
int fct[100005], ifct[100005], inv[100005];
int cmb[100005];
int cc[4005][1005];
int cntall[4005];
class Normalize
{
public:
map<int, int> mp;
vector<int> ord;
void add(int x)
{
if(mp.count(x)) return;
ord.push_back(x);
mp[x];
}
void normalize()
{
sort(ord.begin(), ord.end());
for(int i = 0; i < ord.size(); i++)
mp[ ord[i] ] = i;
}
int get(int x) { return mp[x]; }
}nrm;
int power(int x, int y)
{
if(y <= 0) return 1;
int ans = power( (1LL * x * x) % mod, y >> 1 );
if(y & 1) ans = (1LL * x * ans) % mod;
return ans;
}
void pre(int K)
{
fct[0] = 1;
for(int i = 1; i <= K; i++) fct[i] = (1LL * fct[i - 1] * i) % mod;
ifct[K] = power(fct[K], mod - 2);
for(int i = K - 1; i >= 0; i--) ifct[i] = (1LL * ifct[i + 1] * (i + 1)) % mod;
for(int i = 1; i <= K; i++) inv[i] = power(i, mod - 2);
}
int C(int N, int K)
{
if(K > N) return 0;
int ans = (1LL * fct[N] * ifct[K]) % mod;
ans = (1LL * ans * ifct[N - K]) % mod;
return ans;
}
int main()
{
#ifdef FILE_IO
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
pre(1e4);
scanf("%d", &N);
for(int i = 1; i <= N; i++)
{
scanf("%d%d", &a[i], &b[i]);
nrm.add(a[i]);
nrm.add(b[i]);
}
nrm.normalize();
for(int i = 1; i <= N; i++)
{
st[i] = nrm.get(a[i]);
dr[i] = nrm.get(b[i]);
for(int j = 2 * st[i] + 2; j < 2 * dr[i] + 2; j += 2) cntall[j]++;
}
K = nrm.ord.size();
for(int i = 2; i <= 2 * K - 1; i += 2)
{
int lft = nrm.ord[i / 2 - 1];
int rgt = nrm.ord[i / 2];
int sz = rgt - lft - 1;
cmb[0] = 1;
for(int k = 1; k <= cntall[i]; k++)
{
cmb[k] = (1LL * cmb[k - 1] * (sz - k + 1)) % mod;
cmb[k] = (1LL * cmb[k] * inv[k]) % mod;
}
for(int j = 1; j <= cntall[i]; j++)
for(int k = 0; k < j; k++)
cc[i][j] = (cc[i][j] + (1LL * cmb[k + 1] * C(j - 1, k)) % mod) % mod;
}
for(int i = 0; i <= 2 * K - 1; i++) dp[0][i] = sum[0][i] = 1;
int ans = 0;
for(int i = 1; i <= N; i++)
{
sum[i][0] = sum[i - 1][0];
for(int j = 1; j <= 2 * K - 1; j++)
{
dp[i][j] = dp[i][j - 1];
if(j & 1)
{
int x = nrm.ord[j / 2];
if(a[i] <= x && x <= b[i])
dp[i][j] = (dp[i][j] + sum[i - 1][j - 1]) % mod;
}
else
{
int lft = nrm.ord[j / 2 - 1];
int rgt = nrm.ord[j / 2];
int sz = rgt - lft - 1;
if(a[i] <= lft && rgt <= b[i])
{
cmb[0] = 1;
for(int k = 1; k <= i; k++)
{
cmb[k] = (1LL * cmb[k - 1] * (sz - k + 1)) % mod;
cmb[k] = (1LL * cmb[k] * inv[k]) % mod;
}
int cnt = 0;
for(int k = i; k > 0; k--)
{
if(a[k] <= lft && rgt <= b[k])
cnt++;
int ans = cc[j][cnt];
dp[i][j] += (1LL * dp[k - 1][j - 1] * ans) % mod;
dp[i][j] %= mod;
}
}
}
sum[i][j] = (sum[i - 1][j] + dp[i][j]) % mod;
}
ans = (ans + dp[i][2 * K - 1]) % mod;
}
printf("%d\n", ans);
return 0;
}
Compilation message (stderr)
boat.cpp: In member function 'void Normalize::normalize()':
boat.cpp:33:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < ord.size(); i++)
^
boat.cpp: In function 'int main()':
boat.cpp:75:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
^
boat.cpp:78:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a[i], &b[i]);
^
# | 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... |