| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 694635 |
2023-02-04T07:32:22 Z |
cig32 |
Boat (APIO16_boat) |
C++17 |
|
2000 ms |
6228 KB |
#include "bits/stdc++.h"
#define int long long
#define double long double
using namespace std;
mt19937_64 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
return uniform_int_distribution<int>(x, y)(rng);
}
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
int bm(int b, int p) {
if(p==0) return 1;
int r = bm(b, p/2);
if(p & 1) return (((r*r) % MOD) * b )% MOD;
return (r*r) % MOD;
}
int inv(int b) {
return bm(b, MOD - 2);
}
int nCr(int n, int r) {
if(n < r) return 0;
int ans = 1;
if(r > n-r) r = n-r;
for(int i=1; i<=r; i++) ans = (ans * inv(i)) % MOD;
for(int i=n-r+1; i<=n; i++) ans = (ans * i) % MOD;
return ans;
}
void solve(int tc) {
int n;
cin >> n;
int fac[n+1], invnums[n+1];
fac[0] = 1;
for(int i=1; i<=n; i++) {
fac[i] = (fac[i-1] * i) % MOD;
invnums[i] = inv(i);
}
pair<int, int> p[n+1];
for(int i=1; i<=n; i++) cin >> p[i].first >> p[i].second;
set<int> starts, ends;
for(int i=1; i<=n; i++) {
starts.insert(p[i].first);
ends.insert(p[i].second);
}
starts.insert(MOD);
ends.insert(MOD);
set<pair<int, int> > temp;
for(int i=1; i<=n; i++) {
int now = p[i].first;
while(1) {
int one = *starts.lower_bound(now+1);
int two = *ends.lower_bound(now);
int res = min(one - 1, two);
res = min(res, p[i].second);
temp.insert({now, res});
if(res == p[i].second) break;
now = res+1;
}
}
vector<pair<int, int> > ranges;
ranges.push_back({-1, -1});
for(pair<int, int> x: temp) ranges.push_back(x);
int m = ranges.size()-1; // O(n)
int dp[n+1][m+1]; // O(n^2)
int sum[n+1][m+1]; // sum[i][j] = sum(dp[i][0], dp[i][1], ..., dp[i][j])
/*
dp[i][j] = Number of ways, using the first i students only,
and guarantee using the i-th. With the i-th using the j-th range.
*/
for(int i=0; i<=n; i++) {
for(int j=0; j<=m; j++) {
dp[i][j] = sum[i][j] = 0;
}
}
dp[0][0] = 1;
for(int i=0; i<=m; i++) sum[0][i] = 1;
int pre[m+1][n+1];
for(int i=1; i<=m; i++) {
int L = ranges[i].second - ranges[i].first + 1;
for(int j=0; j<=n; j++) {
pre[i][j] = 0;
for(int x=0; x<=j; x++) pre[i][j] = (pre[i][j] + nCr(j, x) * nCr(L, x+2)) % MOD;
}
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) { // O(n)
if(p[i].first <= ranges[j].first && ranges[j].second <= p[i].second) {
// Consider taking different ranges
for(int k=0; k<i; k++) {
dp[i][j] += sum[k][j-1];
dp[i][j] %= MOD;
}
// Consider taking same ranges
int totn = 0;
int L = ranges[j].second-ranges[j].first+1;
int ps[i+1];
ps[0] = sum[0][j-1];
for(int k=1; k<=i; k++) ps[k] = (ps[k-1] + sum[k][j-1]) % MOD;
for(int k=i-1; k>=0; k--) { // O(n^3)
if(p[k].first <= ranges[j].first && ranges[j].second <= p[k].second) {
dp[i][j] += pre[j][totn] * (k==0 ? 0 : ps[k-1]);
dp[i][j] %= MOD;
}
if(k > 0) totn += (p[k].first <= ranges[j].first && ranges[j].second <= p[k].second);
}
}
sum[i][j] = sum[i][j-1] + dp[i][j];
sum[i][j] %= MOD;
}
}
int answer = 0;
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) answer = (answer + dp[i][j]) % MOD;
cout << answer << "\n";
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int t=1; //cin>>t;
for(int i=1; i<=t; i++) solve(i);
}
/*
If there are totn instances of range j in between k<x<i
Then let the range size = L
Possibilities:
Take 0 from totn: nCr(totn, 0) * nCr(L, 1)
Take x from totn: nCr(totn, x) * nCr(L, x+1)
Answer is sum of nCr(totn, x) * nCr(L, x+1) from 0 <= x <= totn
L can be very large
*/
Compilation message
boat.cpp: In function 'void solve(long long int)':
boat.cpp:99:13: warning: unused variable 'L' [-Wunused-variable]
99 | int L = ranges[j].second-ranges[j].first+1;
| ^
boat.cpp:35:17: warning: variable 'invnums' set but not used [-Wunused-but-set-variable]
35 | int fac[n+1], invnums[n+1];
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2094 ms |
6228 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2094 ms |
6228 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2055 ms |
724 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2094 ms |
6228 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
