oj.uz

Submission #795951

# Submission time Handle Problem Language Result Execution time Memory
795951 2023-07-28T00:46:10 Z bane Boat (APIO16_boat) C++17
9 / 100
 685 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)%mod) % 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-2){
    		//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;
    }

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 8148 KB Output is correct
2 Correct 62 ms 8176 KB Output is correct
3 Correct 63 ms 8184 KB Output is correct
4 Correct 62 ms 8180 KB Output is correct
5 Correct 61 ms 8148 KB Output is correct
6 Correct 63 ms 8176 KB Output is correct
7 Correct 62 ms 8172 KB Output is correct
8 Correct 62 ms 8148 KB Output is correct
9 Correct 62 ms 8148 KB Output is correct
10 Correct 62 ms 8148 KB Output is correct
11 Correct 62 ms 8172 KB Output is correct
12 Correct 62 ms 8168 KB Output is correct
13 Correct 64 ms 8176 KB Output is correct
14 Correct 62 ms 8168 KB Output is correct
15 Correct 63 ms 8176 KB Output is correct
16 Correct 11 ms 1620 KB Output is correct
17 Correct 12 ms 1748 KB Output is correct
18 Correct 12 ms 1748 KB Output is correct
19 Correct 12 ms 1844 KB Output is correct
20 Correct 12 ms 1800 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 8148 KB Output is correct
2 Correct 62 ms 8176 KB Output is correct
3 Correct 63 ms 8184 KB Output is correct
4 Correct 62 ms 8180 KB Output is correct
5 Correct 61 ms 8148 KB Output is correct
6 Correct 63 ms 8176 KB Output is correct
7 Correct 62 ms 8172 KB Output is correct
8 Correct 62 ms 8148 KB Output is correct
9 Correct 62 ms 8148 KB Output is correct
10 Correct 62 ms 8148 KB Output is correct
11 Correct 62 ms 8172 KB Output is correct
12 Correct 62 ms 8168 KB Output is correct
13 Correct 64 ms 8176 KB Output is correct
14 Correct 62 ms 8168 KB Output is correct
15 Correct 63 ms 8176 KB Output is correct
16 Correct 11 ms 1620 KB Output is correct
17 Correct 12 ms 1748 KB Output is correct
18 Correct 12 ms 1748 KB Output is correct
19 Correct 12 ms 1844 KB Output is correct
20 Correct 12 ms 1800 KB Output is correct
21 Incorrect 685 ms 10532 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 8148 KB Output is correct
2 Correct 62 ms 8176 KB Output is correct
3 Correct 63 ms 8184 KB Output is correct
4 Correct 62 ms 8180 KB Output is correct
5 Correct 61 ms 8148 KB Output is correct
6 Correct 63 ms 8176 KB Output is correct
7 Correct 62 ms 8172 KB Output is correct
8 Correct 62 ms 8148 KB Output is correct
9 Correct 62 ms 8148 KB Output is correct
10 Correct 62 ms 8148 KB Output is correct
11 Correct 62 ms 8172 KB Output is correct
12 Correct 62 ms 8168 KB Output is correct
13 Correct 64 ms 8176 KB Output is correct
14 Correct 62 ms 8168 KB Output is correct
15 Correct 63 ms 8176 KB Output is correct
16 Correct 11 ms 1620 KB Output is correct
17 Correct 12 ms 1748 KB Output is correct
18 Correct 12 ms 1748 KB Output is correct
19 Correct 12 ms 1844 KB Output is correct
20 Correct 12 ms 1800 KB Output is correct
21 Incorrect 685 ms 10532 KB Output isn't correct
22 Halted 0 ms 0 KB -