oj.uz

Submission #42617

# Submission time Handle Problem Language Result Execution time Memory
42617 2018-03-01T13:49:48 Z fefe Boat (APIO16_boat) C++14
9 / 100
 18 ms 748 KB 
#include<bits/stdc++.h>
#define MAX_N 505
#define mod 1000000007LL
#define pb push_back
typedef long long LL;
using namespace std;
struct node{
	LL s,e;
}arr[MAX_N];
LL n,ans,inv[10*MAX_N];
LL t[MAX_N],sum[MAX_N],ss[MAX_N];
vector<LL> X,lst;
LL Pow(LL x,LL y){
	if(y==0)	return 1;
	if(y==1)	return x;
	LL z=pow(x,y/2);
	z*=z;z%=mod;
	if(y%2)	z*=x;
	z%=mod;
	return z;
}
int main(){
	LL i,j,k,s,e,x,y,S,E,cnt,p;
	scanf("%lld",&n);
	for(i=1;i<=n;i++){
		scanf("%lld %lld",&arr[i].s,&arr[i].e);
		arr[i].e++;
		X.pb(arr[i].s);X.pb(arr[i].e);
	}
	for(i=1;i<=4000;i++)	inv[i]=Pow(i,mod-2);
	sort(X.begin(),X.end());X.erase(unique(X.begin(),X.end()),X.end());
	LL sz=X.size();
	ss[0]=1;
	for(i=0;i<=n;i++)	sum[i]=1;
	for(i=1;i<sz;i++){
		s=X[i-1];
		e=X[i];
		lst.resize(0);
		sum[0]=1;
		for(j=1;j<=n;j++){
			if(arr[j].e>=e && arr[j].s<=s)	lst.pb(j);
		}
		p=e-s;
		y=lst.size();
		for(j=0;j<y;j++)	t[j]=(p*sum[lst[j]-1]+(j?t[j-1]:0))%mod;
		for(j=2;j<=y && j<=p;j++){
			for(k=y-1;k>=j-1;k--)	t[k]=(t[k]+(t[k-1]*(p-j+1))%mod*inv[j])%mod;
			for(k=0;k<y;k++)	t[k]=(t[k]+(j?t[k-1]:0))%mod;
		}
		for(j=y-1;j>=0;j--)	t[j]=(t[j]+mod-(j?t[j-1]:0))%mod;
		x=0;
		sum[0]=1;
		for(j=1;j<=n;j++){
			if(x!=y && lst[x]==j){
				ss[j]=(ss[j]+t[x])%mod;
				x++;
			}
			sum[j]=(sum[j-1]+ss[j])%mod;
		}
	}
	printf("%lld\n",(sum[n]-1+mod)%mod);
	return 0;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:23:19: warning: unused variable 'S' [-Wunused-variable]
  LL i,j,k,s,e,x,y,S,E,cnt,p;
                   ^
boat.cpp:23:21: warning: unused variable 'E' [-Wunused-variable]
  LL i,j,k,s,e,x,y,S,E,cnt,p;
                     ^
boat.cpp:23:23: warning: unused variable 'cnt' [-Wunused-variable]
  LL i,j,k,s,e,x,y,S,E,cnt,p;
                       ^
boat.cpp:24:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
                  ^
boat.cpp:26:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&arr[i].s,&arr[i].e);
                                         ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 376 KB Output is correct
2 Correct 8 ms 376 KB Output is correct
3 Correct 8 ms 552 KB Output is correct
4 Correct 8 ms 620 KB Output is correct
5 Correct 8 ms 620 KB Output is correct
6 Correct 7 ms 620 KB Output is correct
7 Correct 7 ms 620 KB Output is correct
8 Correct 7 ms 620 KB Output is correct
9 Correct 7 ms 620 KB Output is correct
10 Correct 7 ms 620 KB Output is correct
11 Correct 7 ms 620 KB Output is correct
12 Correct 7 ms 620 KB Output is correct
13 Correct 7 ms 620 KB Output is correct
14 Correct 7 ms 620 KB Output is correct
15 Correct 7 ms 620 KB Output is correct
16 Correct 3 ms 620 KB Output is correct
17 Correct 3 ms 620 KB Output is correct
18 Correct 3 ms 620 KB Output is correct
19 Correct 3 ms 620 KB Output is correct
20 Correct 3 ms 692 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 376 KB Output is correct
2 Correct 8 ms 376 KB Output is correct
3 Correct 8 ms 552 KB Output is correct
4 Correct 8 ms 620 KB Output is correct
5 Correct 8 ms 620 KB Output is correct
6 Correct 7 ms 620 KB Output is correct
7 Correct 7 ms 620 KB Output is correct
8 Correct 7 ms 620 KB Output is correct
9 Correct 7 ms 620 KB Output is correct
10 Correct 7 ms 620 KB Output is correct
11 Correct 7 ms 620 KB Output is correct
12 Correct 7 ms 620 KB Output is correct
13 Correct 7 ms 620 KB Output is correct
14 Correct 7 ms 620 KB Output is correct
15 Correct 7 ms 620 KB Output is correct
16 Correct 3 ms 620 KB Output is correct
17 Correct 3 ms 620 KB Output is correct
18 Correct 3 ms 620 KB Output is correct
19 Correct 3 ms 620 KB Output is correct
20 Correct 3 ms 692 KB Output is correct
21 Incorrect 18 ms 748 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 376 KB Output is correct
2 Correct 8 ms 376 KB Output is correct
3 Correct 8 ms 552 KB Output is correct
4 Correct 8 ms 620 KB Output is correct
5 Correct 8 ms 620 KB Output is correct
6 Correct 7 ms 620 KB Output is correct
7 Correct 7 ms 620 KB Output is correct
8 Correct 7 ms 620 KB Output is correct
9 Correct 7 ms 620 KB Output is correct
10 Correct 7 ms 620 KB Output is correct
11 Correct 7 ms 620 KB Output is correct
12 Correct 7 ms 620 KB Output is correct
13 Correct 7 ms 620 KB Output is correct
14 Correct 7 ms 620 KB Output is correct
15 Correct 7 ms 620 KB Output is correct
16 Correct 3 ms 620 KB Output is correct
17 Correct 3 ms 620 KB Output is correct
18 Correct 3 ms 620 KB Output is correct
19 Correct 3 ms 620 KB Output is correct
20 Correct 3 ms 692 KB Output is correct
21 Incorrect 18 ms 748 KB Output isn't correct
22 Halted 0 ms 0 KB -