oj.uz

Submission #390643

# Submission time Handle Problem Language Result Execution time Memory
390643 2021-04-16T12:52:43 Z Blagojce Boat (APIO16_boat) C++11
0 / 100
 2000 ms 400 KB 
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)


using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int i_inf = 1e9;
const ll inf = 1e10;
const ll mod = 1e9+7;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;

mt19937 _rand(time(NULL));
clock_t z;

const int mxn = 105;


ll modpow(ll x, ll n){
	if(n == 0) return 1%mod;
	ll u = modpow(x, n/2);
	u = (u * u) % mod;
	if(n % 2) u = (u * x) % mod;
	return u;
}
ll inverse(ll x){
	return modpow(x, mod-2);
}

ll fakt[mxn];
ll ifakt[mxn];

ll bc1(ll n, ll k){
	if(n < k) return inverse(0);
	return (fakt[n]*((ifakt[k]*ifakt[n-k]) % mod)) % mod;
}

ll precomp[mxn];

void pre(ll n){
	ll tot = 1;
	precomp[0] = 1;
	fr(i, 0, mxn-1){
		tot *= (n-i);
		tot %= mod;
		precomp[i+1] = tot;
	}
}
ll bc2(ll n, ll k){
	if(n < k) return 0;
	
	return (precomp[k]*ifakt[k])%mod;
}

ll store[mxn][mxn];

void pre2(ll a_len){
	fr(LEN, 2, mxn){
		store[LEN][0] = 0;
		store[LEN][1] = 0;
		fr(len, 2, mxn){
			ll ways = (bc2(a_len, len)*bc1(LEN, len-2))%mod;
			store[LEN][len] = store[LEN][len-1] + ways;
			store[LEN][len] %= mod;
		}
	}
}



int n;
ll l[mxn], r[mxn];

ll DP1[mxn];
ll DP2[mxn];


void solve(){
	fakt[0] = 1;
	fr(i, 1, mxn){
		fakt[i] = (fakt[i-1]*i)%mod;
	}
	fr(i, 0, mxn){
		ifakt[i] = inverse(fakt[i]);
	}
	
	
	
	cin >> n;
	fr(i, 0, n){
		cin >> l[i] >> r[i];
	}
	
	vector<pair<ll, int> > v;
	fr(i, 0, n){
		v.pb({l[i], -i});
		v.pb({r[i],i+1});
	}
	
	sort(all(v));
	
	vector<int> active;
	
	DP1[0] = 1;
	
	ll prv = 0;
	
	ll a_len;
	
	for(auto u : v){
		
		int id = u.nd;
		
		if(id > 0){
			a_len = u.st - prv;
		}
		else{
			a_len = u.st - prv-1;
		}
				
		fr(i, 0, mxn) DP2[i] = DP1[i];
		
		pre(a_len);
		
		
		pre2(a_len);
		
		
		fr(i, 0, (int)active.size()){
			ll sum = 0;
			fr(k, 0, active[i]+1){
				sum += DP1[k];
				sum %= mod;
			}
			
			fr(j, i, (int)active.size()){
				
				if(i == j){
					ll ways = a_len % mod;

					DP2[active[j]+1] += (ways*sum)%mod;
					DP2[active[j]+1] %= mod;
				}
				else{
					DP2[active[j]+1] += (store[j-i+1][j-i+1] * sum) % mod;
				}	
			}
		}
		
		fr(i, 0, mxn){
			DP1[i] = DP2[i];
		}
		
		if(id <= 0){
			prv = u.st-1; 
			active.pb(-id);
			sort(all(active));
			
		}else{
			prv = u.st;
			active.erase(find(all(active), id-1));
			sort(all(active));
		}
		
		
	}
	ll ans = 0;
	fr(i, 1, n+1){
		ans += DP1[i];
		ans %= mod;
	}
	
	cout<<ans<<endl;
}

int main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2068 ms 332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2068 ms 332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2068 ms 332 KB Time limit exceeded
2 Halted 0 ms 0 KB -