oj.uz

Submission #1106250

# Submission time Handle Problem Language Result Execution time Memory
1106250 2024-10-29T16:33:15 Z _rain_ Boat (APIO16_boat) C++14
9 / 100
 785 ms 5752 KB 
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll ;
typedef pair<int,int> ii;
#define fi first
#define se second
#define name "main"
 
const int N=(int)500;
const int MOD=(int)1e9+7;
	int add(int a,int b){
		return a+b>=MOD?a+b-MOD:a+b;
	}
	int sub(int a,int b){
		return a-b<0?a-b+MOD:a-b;
	}
	int mul(int a,int b){
		return (ll)a*b%MOD;
	}
	int power(int a,int b){
		int res=1;
		for(;b;b>>=1,a=mul(a,a))
			if (b&1) res=mul(res,a);
		return res;
	}
vector<int>nen;
vector<ii>line;
int a[N+2],b[N+2],n;
int L[N+2]={},R[N+2]={},f[N*3+2][N+2]={},dp[N+2][N*3+2]={};
int sing[N+2]={},fact[N+2]={},inv[N+2]={},w[N+2]={};
int Combine(int x,int y){
	if (x>y) return 0;
	return (ll)fact[y]*inv[y-x]%MOD*inv[x]%MOD;
}

int C(int k,int n){
	if (k>n) return 0;
	int res=1;
	for(int i=n-k+1;i<=n;++i) res=mul(res,i);
	return mul(res,inv[k]);
}
bool intersec(ii x,int a,int b){
	if (b<x.fi||a>x.se) return false;
	return true;
}
 
void build(){
	memset(L,0x3f,sizeof L);
	memset(R,-0x3f,sizeof R);
	fact[0]=1;
	for(int i=1;i<=N;++i) fact[i]=mul(fact[i-1],i);
	inv[N]=power(fact[N],MOD-2);
	for(int i=N;i>=1;--i) inv[i-1]=mul(inv[i],i);
	for(int id=1;id<=line.size();++id){
		int dodai=line[id-1].se-line[id-1].fi+1;
		for(int j=1;j<=min(dodai,n);++j) w[j]=C(j,dodai);
		for(int j=1;j<=min(dodai+1,n);++j){
			for(int c=1;c<=j;++c)
				f[id][j]=add(f[id][j],mul(Combine(c-1,j-1),w[c]));
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=line.size();++j){
			if (intersec(line[j-1],a[i],b[i])) 
				L[i]=min(L[i],j),R[i]=max(R[i],j);
		}
	}
	return;
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//freopen(name".inp","r",stdin);
	//freopen(name".out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i]>>b[i];
		nen.push_back(a[i]);
		nen.push_back(b[i]);
		nen.push_back(a[i]-1);
	}
	sort(nen.begin(),nen.end());
	nen.resize(unique(nen.begin(),nen.end())-nen.begin());
	for(int i=1;i<nen.size();++i){
		if (i-1==0) line.push_back({nen[i-1],nen[i]});
		else line.push_back({nen[i-1]+1,nen[i]});
	}
	// cout<<nen.size()<<'\n';
	build();
	for(int i=0;i<=line.size();++i) dp[0][i]=1;
	for(int i=1;i<=n;++i){
		// cout<<i<<'\n';
		for(int id=L[i];id<=R[i];++id){
			int cnt=0;
			pair<int,int> xx=line[id-1];
			if (id==L[i]){
				int dodai=line[id-1].se-a[i]+1;
				for(int j=0;j<=i;++j) sing[j]=0;
				for(int j=1;j<=i;++j) w[j]=C(j,dodai);
				for(int j=1;j<=i;++j){
					for(int c=1;c<=j;++c)
						sing[j]=add(sing[j],mul(Combine(c-1,j),w[c]));
				}
				xx={a[i],line[id-1].se};
			}
			for(int j=i;j>=1;--j){
				if (intersec(xx,a[j],b[j])) ++cnt;
				if (id==L[i]) dp[i][id]=add(dp[i][id],mul(sing[cnt],dp[j-1][id-1]));
				else dp[i][id]=add(dp[i][id],mul(f[id][cnt],dp[j-1][id-1]));
			}
		}
		for(int j=L[i];j<=line.size();++j) dp[i][j]=add(dp[i][j],dp[i][j-1]);
	}
	int ans=0;
	for(int i=1;i<=n;++i) ans=add(ans,dp[i][line.size()]);
	cout<<ans;
	exit(0);
}

Compilation message

boat.cpp: In function 'void build()':
boat.cpp:55:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(int id=1;id<=line.size();++id){
      |               ~~^~~~~~~~~~~~~
boat.cpp:64:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for(int j=1;j<=line.size();++j){
      |               ~^~~~~~~~~~~~~
boat.cpp: In function 'int32_t main()':
boat.cpp:86:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  for(int i=1;i<nen.size();++i){
      |              ~^~~~~~~~~~~
boat.cpp:92:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for(int i=0;i<=line.size();++i) dp[0][i]=1;
      |              ~^~~~~~~~~~~~~
boat.cpp:114:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |   for(int j=L[i];j<=line.size();++j) dp[i][j]=add(dp[i][j],dp[i][j-1]);
      |                  ~^~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 760 ms 5016 KB Output is correct
2 Correct 762 ms 5104 KB Output is correct
3 Correct 764 ms 4936 KB Output is correct
4 Correct 772 ms 4908 KB Output is correct
5 Correct 785 ms 4984 KB Output is correct
6 Correct 769 ms 5192 KB Output is correct
7 Correct 766 ms 5084 KB Output is correct
8 Correct 766 ms 4936 KB Output is correct
9 Correct 769 ms 5032 KB Output is correct
10 Correct 768 ms 5192 KB Output is correct
11 Correct 767 ms 5156 KB Output is correct
12 Correct 776 ms 4936 KB Output is correct
13 Correct 767 ms 4936 KB Output is correct
14 Correct 761 ms 4980 KB Output is correct
15 Correct 761 ms 4936 KB Output is correct
16 Correct 229 ms 2888 KB Output is correct
17 Correct 240 ms 2848 KB Output is correct
18 Correct 237 ms 2860 KB Output is correct
19 Correct 246 ms 2888 KB Output is correct
20 Correct 238 ms 2880 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 760 ms 5016 KB Output is correct
2 Correct 762 ms 5104 KB Output is correct
3 Correct 764 ms 4936 KB Output is correct
4 Correct 772 ms 4908 KB Output is correct
5 Correct 785 ms 4984 KB Output is correct
6 Correct 769 ms 5192 KB Output is correct
7 Correct 766 ms 5084 KB Output is correct
8 Correct 766 ms 4936 KB Output is correct
9 Correct 769 ms 5032 KB Output is correct
10 Correct 768 ms 5192 KB Output is correct
11 Correct 767 ms 5156 KB Output is correct
12 Correct 776 ms 4936 KB Output is correct
13 Correct 767 ms 4936 KB Output is correct
14 Correct 761 ms 4980 KB Output is correct
15 Correct 761 ms 4936 KB Output is correct
16 Correct 229 ms 2888 KB Output is correct
17 Correct 240 ms 2848 KB Output is correct
18 Correct 237 ms 2860 KB Output is correct
19 Correct 246 ms 2888 KB Output is correct
20 Correct 238 ms 2880 KB Output is correct
21 Incorrect 336 ms 5752 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 760 ms 5016 KB Output is correct
2 Correct 762 ms 5104 KB Output is correct
3 Correct 764 ms 4936 KB Output is correct
4 Correct 772 ms 4908 KB Output is correct
5 Correct 785 ms 4984 KB Output is correct
6 Correct 769 ms 5192 KB Output is correct
7 Correct 766 ms 5084 KB Output is correct
8 Correct 766 ms 4936 KB Output is correct
9 Correct 769 ms 5032 KB Output is correct
10 Correct 768 ms 5192 KB Output is correct
11 Correct 767 ms 5156 KB Output is correct
12 Correct 776 ms 4936 KB Output is correct
13 Correct 767 ms 4936 KB Output is correct
14 Correct 761 ms 4980 KB Output is correct
15 Correct 761 ms 4936 KB Output is correct
16 Correct 229 ms 2888 KB Output is correct
17 Correct 240 ms 2848 KB Output is correct
18 Correct 237 ms 2860 KB Output is correct
19 Correct 246 ms 2888 KB Output is correct
20 Correct 238 ms 2880 KB Output is correct
21 Incorrect 336 ms 5752 KB Output isn't correct
22 Halted 0 ms 0 KB -