| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 795949 |
2023-07-28T00:43:22 Z |
bane |
Boat (APIO16_boat) |
C++17 |
|
693 ms |
10532 KB |
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
/*
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
#define rep1n(i, n) for (int i = 1; i <= (n); ++i)
#define repr(i, n) for (int i = (n) - 1; i >= 0; --i)
#define fr first
#define sc second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;
const int nax = (int)501;
const int mod = (int)1e9 + 7;
int a[nax], b[nax];
ll bpow(ll a, ll b){
ll res = 1;
while(b){
if (b & 1)
res = (a * res) % mod;
b /= 2;
a = (a * a) % mod;
}
return res;
}
ll O = bpow(2,mod - 2);
ll c (ll a){
return (((a * (a - 1))%mod) * O)%mod;
}
void solve(){
int n;
cin >> n;
vector<int>pts;
rep1n(i,n){
cin >> a[i] >> b[i];
pts.pb(a[i]);
pts.pb(b[i]);
pts.pb(b[i] + 1);
}
pts.push_back(0);
sort(all(pts));
pts.erase(unique(all(pts)), pts.end());
int m = pts.size();
ll dp[n + 1][m + 1];
memset(dp, 0LL, sizeof(dp));
dp[0][0] = 1;
ll choose[m + 1][n + 1];
rep(i,m - 1){
choose[i][1] = pts[i + 1] - pts[i];
for(int j = 2; j <= n; j++){
choose[i][j] = (choose[i][j - 1] * bpow(j, mod - 2) % mod) * (pts[i + 1] - pts[i] - j + 1) % mod;
}
}
ll orz[m + 1];
memset(orz, 0, sizeof(orz));
rep1n(i,n){
rep(j,m){
dp[i][j] = dp[i - 1][j];
//cout << dp[i][j] << " ";
}
rep(j,m - 1){
if (a[i] <= pts[j] && pts[j + 1] <= b[i] + 1){
//in range [L, R)
ll factor = 0;
orz[j]++;
rep1n(p, orz[j]){
factor += choose[j][p];
factor %= mod;
}
repr(k,j){
//dp[i-1][k]
dp[i][j] += dp[i - 1][k] * factor % mod;
dp[i][j] %= mod;
}
}
}
}
ll ans = 0;
rep1n(i,m-1){
//cout << dp[n][i] << endl;
ans += dp[n][i];
ans %= mod;
}
cout << ans << '\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int tt = 1;
//cin >> tt;
while(tt--){
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
8176 KB |
Output is correct |
| 2 |
Correct |
63 ms |
8184 KB |
Output is correct |
| 3 |
Correct |
62 ms |
8176 KB |
Output is correct |
| 4 |
Correct |
63 ms |
8184 KB |
Output is correct |
| 5 |
Correct |
62 ms |
8192 KB |
Output is correct |
| 6 |
Correct |
63 ms |
8176 KB |
Output is correct |
| 7 |
Correct |
63 ms |
8176 KB |
Output is correct |
| 8 |
Correct |
62 ms |
8176 KB |
Output is correct |
| 9 |
Correct |
62 ms |
8172 KB |
Output is correct |
| 10 |
Correct |
62 ms |
8176 KB |
Output is correct |
| 11 |
Correct |
62 ms |
8180 KB |
Output is correct |
| 12 |
Correct |
62 ms |
8176 KB |
Output is correct |
| 13 |
Correct |
62 ms |
8188 KB |
Output is correct |
| 14 |
Correct |
64 ms |
8188 KB |
Output is correct |
| 15 |
Correct |
61 ms |
8148 KB |
Output is correct |
| 16 |
Correct |
11 ms |
1620 KB |
Output is correct |
| 17 |
Correct |
12 ms |
1844 KB |
Output is correct |
| 18 |
Correct |
11 ms |
1748 KB |
Output is correct |
| 19 |
Correct |
12 ms |
1748 KB |
Output is correct |
| 20 |
Correct |
12 ms |
1800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
8176 KB |
Output is correct |
| 2 |
Correct |
63 ms |
8184 KB |
Output is correct |
| 3 |
Correct |
62 ms |
8176 KB |
Output is correct |
| 4 |
Correct |
63 ms |
8184 KB |
Output is correct |
| 5 |
Correct |
62 ms |
8192 KB |
Output is correct |
| 6 |
Correct |
63 ms |
8176 KB |
Output is correct |
| 7 |
Correct |
63 ms |
8176 KB |
Output is correct |
| 8 |
Correct |
62 ms |
8176 KB |
Output is correct |
| 9 |
Correct |
62 ms |
8172 KB |
Output is correct |
| 10 |
Correct |
62 ms |
8176 KB |
Output is correct |
| 11 |
Correct |
62 ms |
8180 KB |
Output is correct |
| 12 |
Correct |
62 ms |
8176 KB |
Output is correct |
| 13 |
Correct |
62 ms |
8188 KB |
Output is correct |
| 14 |
Correct |
64 ms |
8188 KB |
Output is correct |
| 15 |
Correct |
61 ms |
8148 KB |
Output is correct |
| 16 |
Correct |
11 ms |
1620 KB |
Output is correct |
| 17 |
Correct |
12 ms |
1844 KB |
Output is correct |
| 18 |
Correct |
11 ms |
1748 KB |
Output is correct |
| 19 |
Correct |
12 ms |
1748 KB |
Output is correct |
| 20 |
Correct |
12 ms |
1800 KB |
Output is correct |
| 21 |
Incorrect |
693 ms |
10532 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
8176 KB |
Output is correct |
| 2 |
Correct |
63 ms |
8184 KB |
Output is correct |
| 3 |
Correct |
62 ms |
8176 KB |
Output is correct |
| 4 |
Correct |
63 ms |
8184 KB |
Output is correct |
| 5 |
Correct |
62 ms |
8192 KB |
Output is correct |
| 6 |
Correct |
63 ms |
8176 KB |
Output is correct |
| 7 |
Correct |
63 ms |
8176 KB |
Output is correct |
| 8 |
Correct |
62 ms |
8176 KB |
Output is correct |
| 9 |
Correct |
62 ms |
8172 KB |
Output is correct |
| 10 |
Correct |
62 ms |
8176 KB |
Output is correct |
| 11 |
Correct |
62 ms |
8180 KB |
Output is correct |
| 12 |
Correct |
62 ms |
8176 KB |
Output is correct |
| 13 |
Correct |
62 ms |
8188 KB |
Output is correct |
| 14 |
Correct |
64 ms |
8188 KB |
Output is correct |
| 15 |
Correct |
61 ms |
8148 KB |
Output is correct |
| 16 |
Correct |
11 ms |
1620 KB |
Output is correct |
| 17 |
Correct |
12 ms |
1844 KB |
Output is correct |
| 18 |
Correct |
11 ms |
1748 KB |
Output is correct |
| 19 |
Correct |
12 ms |
1748 KB |
Output is correct |
| 20 |
Correct |
12 ms |
1800 KB |
Output is correct |
| 21 |
Incorrect |
693 ms |
10532 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
