oj.uz

Submission #45603

# Submission time Handle Problem Language Result Execution time Memory
45603 2018-04-15T16:00:48 Z gnoor Boat (APIO16_boat) C++17
9 / 100
 1606 ms 134480 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 134264 KB Output is correct
2 Correct 123 ms 134368 KB Output is correct
3 Correct 132 ms 134368 KB Output is correct
4 Correct 123 ms 134420 KB Output is correct
5 Correct 124 ms 134420 KB Output is correct
6 Correct 122 ms 134428 KB Output is correct
7 Correct 145 ms 134428 KB Output is correct
8 Correct 121 ms 134428 KB Output is correct
9 Correct 142 ms 134476 KB Output is correct
10 Correct 119 ms 134476 KB Output is correct
11 Correct 122 ms 134476 KB Output is correct
12 Correct 121 ms 134480 KB Output is correct
13 Correct 129 ms 134480 KB Output is correct
14 Correct 159 ms 134480 KB Output is correct
15 Correct 123 ms 134480 KB Output is correct
16 Correct 28 ms 134480 KB Output is correct
17 Correct 32 ms 134480 KB Output is correct
18 Correct 38 ms 134480 KB Output is correct
19 Correct 31 ms 134480 KB Output is correct
20 Correct 30 ms 134480 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 134264 KB Output is correct
2 Correct 123 ms 134368 KB Output is correct
3 Correct 132 ms 134368 KB Output is correct
4 Correct 123 ms 134420 KB Output is correct
5 Correct 124 ms 134420 KB Output is correct
6 Correct 122 ms 134428 KB Output is correct
7 Correct 145 ms 134428 KB Output is correct
8 Correct 121 ms 134428 KB Output is correct
9 Correct 142 ms 134476 KB Output is correct
10 Correct 119 ms 134476 KB Output is correct
11 Correct 122 ms 134476 KB Output is correct
12 Correct 121 ms 134480 KB Output is correct
13 Correct 129 ms 134480 KB Output is correct
14 Correct 159 ms 134480 KB Output is correct
15 Correct 123 ms 134480 KB Output is correct
16 Correct 28 ms 134480 KB Output is correct
17 Correct 32 ms 134480 KB Output is correct
18 Correct 38 ms 134480 KB Output is correct
19 Correct 31 ms 134480 KB Output is correct
20 Correct 30 ms 134480 KB Output is correct
21 Incorrect 1606 ms 134480 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 134264 KB Output is correct
2 Correct 123 ms 134368 KB Output is correct
3 Correct 132 ms 134368 KB Output is correct
4 Correct 123 ms 134420 KB Output is correct
5 Correct 124 ms 134420 KB Output is correct
6 Correct 122 ms 134428 KB Output is correct
7 Correct 145 ms 134428 KB Output is correct
8 Correct 121 ms 134428 KB Output is correct
9 Correct 142 ms 134476 KB Output is correct
10 Correct 119 ms 134476 KB Output is correct
11 Correct 122 ms 134476 KB Output is correct
12 Correct 121 ms 134480 KB Output is correct
13 Correct 129 ms 134480 KB Output is correct
14 Correct 159 ms 134480 KB Output is correct
15 Correct 123 ms 134480 KB Output is correct
16 Correct 28 ms 134480 KB Output is correct
17 Correct 32 ms 134480 KB Output is correct
18 Correct 38 ms 134480 KB Output is correct
19 Correct 31 ms 134480 KB Output is correct
20 Correct 30 ms 134480 KB Output is correct
21 Incorrect 1606 ms 134480 KB Output isn't correct
22 Halted 0 ms 0 KB -