Submission #390631

#	Time	Username	Problem	Language	Result	Execution time	Memory
390631		Blagojce	Boat (APIO16_boat)	C++11	0 / 100	464 ms	344 KiB

boat

#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 = 1000;


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){
		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;
}


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

int DP1[mxn];
int 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<int,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);
		
		
		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()){
				int psz = 1 + (int)(i != j);
				
				
				fr(len, psz, j-i+2){
					ll ways = (bc2(a_len, len)*bc1(i-j+1-psz, len-psz))%mod;
					DP2[active[j]+1] += (ways*sum)%mod;
					DP2[active[j]+1] %= 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, 0, n+1){
		ans += DP1[i];
		ans %= mod;
	}
	--ans;
	if(ans < 0) ans += mod;
	
	cout<<ans<<endl;
	
}

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

Compilation message (stderr)

boat.cpp: In function 'void pre(ll)':
boat.cpp:54:16: warning: iteration 999 invokes undefined behavior [-Waggressive-loop-optimizations]
   54 |   precomp[i+1] = tot;
      |   ~~~~~~~~~~~~~^~~~~
boat.cpp:2:40: note: within this loop
    2 | #define fr(i, n, m) for(int i = (n); i < (m); i ++)
      |                                        ^
boat.cpp:51:2: note: in expansion of macro 'fr'
   51 |  fr(i, 0, mxn){
      |  ^~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42