Submission #45603

#	Time	Username	Problem	Language	Result	Execution time	Memory
45603		gnoor	Boat (APIO16_boat)	C++17	9 / 100	1606 ms	134480 KiB

boat

#include <cstdio>
#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;
	//for (int j=1;j<=n;j++) printf("%lld ",p[0][j]);
	//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-1][j-1]*(1<<(i-1));
			p[i][j]%=mod;
			//printf("%lld ",p[i][j]);
		}
		//printf("\n");
	}
	int val;	
	for (int k=1;k<=nn;k++) {
		val=dec[k]-dec[k-1];	
		for (int j=1;j<=n;j++) {
			if (val%2) {
				q[k][j][0]=j;
			}
			for (int i=1;i<32;i++) {
				if (val&(1<<i)) {
					q[k][j][i]=q[k][j-1][i]+p[i][j]-p[i][j-1]+q[k][j][i-1]-q[k][j-1][i-1]+q[k][j-1][i-1]*(1<<i);
				} else {
					q[k][j][i]=q[k][j][i-1];
				}
			}
			//printf("%lld ",q[k][j][31]);
		}
		//printf("\n");
	}	
	

	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;
			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[k][cnt][31]-q[k][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[k][cnt][31]-q[k][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;
	}
	printf("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
boat.cpp:21: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: 9 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42