oj.uz

Submission #203916

# Submission time Handle Problem Language Result Execution time Memory
203916 2020-02-23T02:56:54 Z Segtree Boat (APIO16_boat) C++14
27 / 100
 2000 ms 30136 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<unordered_map>
using namespace std;
typedef long long ll;
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod
#define mul(a,b) a=a*b%mod
#define N 510
ll po(ll x,ll y){
	ll res=1;
	for(;y;y>>=1){
		if(y&1)mul(res,x);
		x=x*x%mod;
	}
	return res;
}
ll inv[N];
unordered_map<ll,ll> C[N];
void calcc(ll l){
	ll res=1;
	C[0][l]=1;
	for(ll i=1;i<N;i++){
		mul(res,(l+1LL-i));
		mul(res,inv[i]);
		if(i>l)res=0;
		C[i][l]=res;
	}
}
unordered_map<ll,ll> f[N];
void initf(ll l,ll m){
	ll res=0;
	for(int i=1;i<=m;i++){
		mad(res,C[i][l]*C[i-1][m-1]);
	}
	f[m][l]=res;
}

ll n,a[N],b[N];
ll rui[2*N][N];
vector<ll> xs;
ll edge(ll j,ll i,ll ii){
	ll m=rui[j][ii]-rui[j][i];
	return f[m][xs[j+1]-xs[j]];
}

ll dp[N][2*N];
int main(){
	for(int i=1;i<N;i++)inv[i]=po(i,mod-2);
	cin>>n;
	a[0]=b[0]=0;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
	}
	a[n+1]=2e9,b[n+1]=2e9;
	for(int i=0;i<=n+1;i++){
		b[i]++;
		xs.push_back(a[i]);
		xs.push_back(b[i]);
	}
	sort(all(xs));
	xs.erase(unique(all(xs)),xs.end());
	for(int i=0;i<=n+1;i++){
		a[i]=lower_bound(all(xs),a[i])-xs.begin();
		b[i]=lower_bound(all(xs),b[i])-xs.begin();
	}
	rep(i,N)calcc(i);
	for(int i=0;i<xs.size()-1;i++){
		calcc(xs[i+1]-xs[i]);
		for(int m=1;m<N;m++)initf(xs[i+1]-xs[i],m);
	}
	rep(j,xs.size()-1){
		rui[j][0]=0;
		for(int i=0;i<=n+1;i++){
			rui[j][i+1]=rui[j][i]+(a[i]<=j&&j<b[i]);
		}
	}
	for(int i=0;i<=n+1;i++)rep(j,xs.size()-1)dp[i][j]=0;
	dp[0][0]=1;
	for(int ii=1;ii<=n+1;ii++){
		for(int jj=a[ii];jj<b[ii];jj++){
			if(jj>a[ii])mad(dp[ii][jj],dp[ii][jj-1]);
			for(int i=0;i<ii;i++)for(int j=(jj==a[ii]?0:jj-1);j<jj;j++){
				mad(dp[ii][jj],dp[i][j]*edge(j,i,ii));
			}
		}
	}
	ll ans=dp[n+1][a[n+1]]+mod-1; ans%=mod;
	cout<<ans<<endl;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:73:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<xs.size()-1;i++){
              ~^~~~~~~~~~~~
boat.cpp:10:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n) for(int i=0;i<n;i++)
boat.cpp:77:6:
  rep(j,xs.size()-1){
      ~~~~~~~~~~~~~             
boat.cpp:77:2: note: in expansion of macro 'rep'
  rep(j,xs.size()-1){
  ^~~
boat.cpp:10:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n) for(int i=0;i<n;i++)
boat.cpp:83:29:
  for(int i=0;i<=n+1;i++)rep(j,xs.size()-1)dp[i][j]=0;
                             ~~~~~~~~~~~~~
boat.cpp:83:25: note: in expansion of macro 'rep'
  for(int i=0;i<=n+1;i++)rep(j,xs.size()-1)dp[i][j]=0;
                         ^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2086 ms 30136 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 2086 ms 30136 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 663 ms 23996 KB Output is correct
2 Correct 622 ms 23928 KB Output is correct
3 Correct 634 ms 24184 KB Output is correct
4 Correct 610 ms 24320 KB Output is correct
5 Correct 660 ms 24184 KB Output is correct
6 Correct 620 ms 23928 KB Output is correct
7 Correct 627 ms 23928 KB Output is correct
8 Correct 650 ms 24012 KB Output is correct
9 Correct 628 ms 24056 KB Output is correct
10 Correct 623 ms 24056 KB Output is correct
11 Correct 608 ms 24032 KB Output is correct
12 Correct 635 ms 24088 KB Output is correct
13 Correct 626 ms 24056 KB Output is correct
14 Correct 604 ms 24056 KB Output is correct
15 Correct 597 ms 23928 KB Output is correct
16 Correct 373 ms 15828 KB Output is correct
17 Correct 359 ms 15740 KB Output is correct
18 Correct 342 ms 15736 KB Output is correct
19 Correct 331 ms 15864 KB Output is correct
20 Correct 347 ms 15992 KB Output is correct

Subtask #4
0 / 42.0

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