oj.uz

답안 #203909

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
203909 2020-02-23T01:59:32 Z Segtree Boat (APIO16_boat) C++14
9 / 100
 2000 ms 30456 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;
	for(int i=1;i<N;i++){
		mul(res,l);
		mul(res,inv[i]);
		if(i>l)res=0;
		C[i][l]=res;
	}
}
unordered_map<ll,ll> f[N];
void initf(ll l){
	ll res=0;
	for(int i=1;i<N;i++){
		mad(res,C[i][l]);
		f[i][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];
	/*for(int k=i;k<ii;k++){
		if(a[k]<=j&&j<b[k])m++;
	}*/
	//cout<<"edge("<<j<<","<<i<<","<<ii<<")="<<f(xs[j+1]-xs[j],m)<<endl;
	//cout<<"l="<<xs[j+1]-xs[j]<<", m="<<m<<endl;
	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;
	xs.push_back(0); xs.push_back(1);
	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();
	}
	for(int i=0;i<xs.size()-1;i++){
		calcc(xs[i+1]-xs[i]);
		initf(xs[i+1]-xs[i]);
	}
	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++){
			for(int i=0;i<ii;i++)for(int j=0;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:77: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:81:6:
  rep(j,xs.size()-1){
      ~~~~~~~~~~~~~             
boat.cpp:81: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:87:29:
  for(int i=0;i<=n+1;i++)rep(j,xs.size()-1)dp[i][j]=0;
                             ~~~~~~~~~~~~~
boat.cpp:87: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
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1092 ms 30156 KB Output is correct
2 Correct 1120 ms 30072 KB Output is correct
3 Correct 1124 ms 30072 KB Output is correct
4 Correct 1158 ms 30200 KB Output is correct
5 Correct 1168 ms 30200 KB Output is correct
6 Correct 1350 ms 30256 KB Output is correct
7 Correct 1368 ms 30200 KB Output is correct
8 Correct 1396 ms 30200 KB Output is correct
9 Correct 1386 ms 30456 KB Output is correct
10 Correct 1406 ms 30200 KB Output is correct
11 Correct 1369 ms 30456 KB Output is correct
12 Correct 1447 ms 30200 KB Output is correct
13 Correct 1409 ms 30208 KB Output is correct
14 Correct 1682 ms 30200 KB Output is correct
15 Correct 1468 ms 30200 KB Output is correct
16 Correct 126 ms 8056 KB Output is correct
17 Correct 167 ms 8312 KB Output is correct
18 Correct 153 ms 8184 KB Output is correct
19 Correct 126 ms 8312 KB Output is correct
20 Correct 139 ms 8312 KB Output is correct

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1092 ms 30156 KB Output is correct
2 Correct 1120 ms 30072 KB Output is correct
3 Correct 1124 ms 30072 KB Output is correct
4 Correct 1158 ms 30200 KB Output is correct
5 Correct 1168 ms 30200 KB Output is correct
6 Correct 1350 ms 30256 KB Output is correct
7 Correct 1368 ms 30200 KB Output is correct
8 Correct 1396 ms 30200 KB Output is correct
9 Correct 1386 ms 30456 KB Output is correct
10 Correct 1406 ms 30200 KB Output is correct
11 Correct 1369 ms 30456 KB Output is correct
12 Correct 1447 ms 30200 KB Output is correct
13 Correct 1409 ms 30208 KB Output is correct
14 Correct 1682 ms 30200 KB Output is correct
15 Correct 1468 ms 30200 KB Output is correct
16 Correct 126 ms 8056 KB Output is correct
17 Correct 167 ms 8312 KB Output is correct
18 Correct 153 ms 8184 KB Output is correct
19 Correct 126 ms 8312 KB Output is correct
20 Correct 139 ms 8312 KB Output is correct
21 Execution timed out 2077 ms 9336 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 722 ms 11000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1092 ms 30156 KB Output is correct
2 Correct 1120 ms 30072 KB Output is correct
3 Correct 1124 ms 30072 KB Output is correct
4 Correct 1158 ms 30200 KB Output is correct
5 Correct 1168 ms 30200 KB Output is correct
6 Correct 1350 ms 30256 KB Output is correct
7 Correct 1368 ms 30200 KB Output is correct
8 Correct 1396 ms 30200 KB Output is correct
9 Correct 1386 ms 30456 KB Output is correct
10 Correct 1406 ms 30200 KB Output is correct
11 Correct 1369 ms 30456 KB Output is correct
12 Correct 1447 ms 30200 KB Output is correct
13 Correct 1409 ms 30208 KB Output is correct
14 Correct 1682 ms 30200 KB Output is correct
15 Correct 1468 ms 30200 KB Output is correct
16 Correct 126 ms 8056 KB Output is correct
17 Correct 167 ms 8312 KB Output is correct
18 Correct 153 ms 8184 KB Output is correct
19 Correct 126 ms 8312 KB Output is correct
20 Correct 139 ms 8312 KB Output is correct
21 Execution timed out 2077 ms 9336 KB Time limit exceeded
22 Halted 0 ms 0 KB -