Submission #45653

#	Time	Username	Problem	Language	Result	Execution time	Memory
45653		gnoor	Boat (APIO16_boat)	C++17	27 / 100	2064 ms	7956 KiB

boat

#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

map<int,int> mp;
int a[600];
int b[600];
int mod=1000000007;
int dec[1010];

long long dp[600][1010];
long long p[32][600];
long long q[1010][600][32];

int main () {
	int n;
	scanf("%d",&n);
	for (int i=0;i<n;i++) {
		scanf("%d%d",&a[i],&b[i]);
		mp[a[i]-1];
		mp[b[i]];
	}
	int i=1;
	for (auto &ii:mp) {
		dec[i]=ii.first;
		ii.second=i++;
	}
	for (int i=0;i<n;i++) {
		a[i]=mp[a[i]-1];
		b[i]=mp[b[i]];
	}
	int nn=mp.size();

	for (int j=1;j<=n;j++) p[0][j]=j;
	//printf("0: ");
	//for (int j=1;j<=n;j++) printf("%lld ",p[0][j]-p[0][j-1]);
	//printf("\n");
	for (int i=1;i<32;i++) {
		//printf("%d: ",i);
		for (int j=1;j<=n;j++) {
			p[i][j]=2*(p[i-1][j]-p[i-1][j-1]);
			p[i][j]%=mod;
			p[i][j]+=p[i][j-1];
			p[i][j]%=mod;
			for (int k=1;k<j;k++) {
				p[i][j]+=((p[i-1][k]-p[i-1][k-1])%mod)*((p[i-1][j-k]-p[i-1][j-k-1])%mod);
				p[i][j]%=mod;
			}
			//printf("%lld ",p[i][j]-p[i][j-1]);
		}
		//printf("\n");
	}
	vector<int> rng;
	for (int k=1;k<=nn;k++) {
		rng.push_back(dec[k]-dec[k-1]);
	}
	rng.push_back(0);
	sort(rng.begin(),rng.end());
	rng.erase(unique(rng.begin(),rng.end()),rng.end());
	int val;	
	for (int k=1;k<(int)rng.size();k++) {
		val=rng[k];	
		//printf("-- %d\n",val);
		for (int j=1;j<=n;j++) {
			int i=0;
			while ((rng[k]&(1<<(31-i)))==(rng[k-1]&(1<<(31-i)))) {
				q[k][j][i]=q[k-1][j][i];
				i++;
			}
			for (;i<32;i++) {
				//printf("%d\n",31-i);
				//if ((rng[k]&(1<<(31-i)))==(rng[k-1]&(1<<(31-i)))) {
					//printf("y\n");
					//q[k][j][i]=q[k-1][j][i];
					//continue;
				//}	
				if (i==0) {
					if (val%2) q[k][j][0]=p[31][j];
					else q[k][j][0]=0;
					continue;
				}
				if (val&(1<<(31-i))) {
					q[k][j][i]=q[k][j-1][i]+p[31-i][j]-p[31-i][j-1]+q[k][j][i-1]-q[k][j-1][i-1];
					q[k][j][i]%=mod;
					for (int l=1;l<j;l++) {
						q[k][j][i]+=((q[k][l][i-1]-q[k][l-1][i-1])%mod)*((p[31-i][j-l]-p[31-i][j-l-1])%mod);
						q[k][j][i]%=mod;
					}
				} else {
					q[k][j][i]=q[k][j][i-1];
				}
				//printf("%d,%lld ",i,q[k][j][i]);
			}
			//printf("%lld ",q[k][j][31]);
		}
		//printf("\n");
	}	
	
	int kk;
	for (int i=0;i<n;i++) {
		//printf("** %d %d\n",a[i],b[i]);
		for (int k=a[i]+1;k<=b[i];k++) {
			int cnt=1;
			kk=lower_bound(rng.begin(),rng.end(),dec[k]-dec[k-1])-rng.begin();
			for (int j=i-1;j>=0;j--) {
				//printf("** %d %d %d %lld\n",i,j,k,dp[j][k-1]);
				dp[i][k]+=dp[j][k-1]*(q[kk][cnt][31]-q[kk][cnt-1][31]);
				//dp[i][k]+=dp[j][k-1]*(dec[k]-dec[k-1]);
				dp[i][k]%=mod;
				if (k>a[j]&&k<=b[j]) cnt++;
			}
			dp[i][k]+=q[kk][cnt][31]-q[kk][cnt-1][31];
			dp[i][k]+=dp[i][k-1];
			dp[i][k]%=mod;			
		}
		//for (int k=a[i]+1;k<=b[i];k++) {
			//dp[i][k]+=(dec[k]-dec[k-1]);
			//dp[i][k]+=dp[i][k-1];
			//dp[i][k]%=mod;
		//}
		for (int k=b[i]+1;k<=nn;k++) {
			dp[i][k]+=dp[i][k-1];
			dp[i][k]%=mod;
		}
		//for (int k=1;k<=nn;k++) {
			//printf("%lld ",dp[i][k]);
		//}
		//printf("\n");
	}
	long long ans=0;
	for (int i=0;i<n;i++) {
		ans+=dp[i][nn];
		ans%=mod;
	}
	ans+=mod;
	ans%=mod;
	printf("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
boat.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a[i],&b[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

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