| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 45654 |
2018-04-15T17:40:01 Z |
gnoor |
Boat (APIO16_boat) |
C++17 |
|
2000 ms |
7440 KB |
#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 (i<32&&(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
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]);
~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2045 ms |
6852 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2045 ms |
6852 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
388 ms |
7156 KB |
Output is correct |
| 2 |
Correct |
399 ms |
7156 KB |
Output is correct |
| 3 |
Correct |
400 ms |
7272 KB |
Output is correct |
| 4 |
Correct |
370 ms |
7344 KB |
Output is correct |
| 5 |
Correct |
381 ms |
7384 KB |
Output is correct |
| 6 |
Correct |
373 ms |
7412 KB |
Output is correct |
| 7 |
Correct |
371 ms |
7412 KB |
Output is correct |
| 8 |
Correct |
374 ms |
7412 KB |
Output is correct |
| 9 |
Correct |
366 ms |
7428 KB |
Output is correct |
| 10 |
Correct |
369 ms |
7428 KB |
Output is correct |
| 11 |
Correct |
361 ms |
7428 KB |
Output is correct |
| 12 |
Correct |
390 ms |
7428 KB |
Output is correct |
| 13 |
Correct |
398 ms |
7440 KB |
Output is correct |
| 14 |
Correct |
442 ms |
7440 KB |
Output is correct |
| 15 |
Correct |
370 ms |
7440 KB |
Output is correct |
| 16 |
Correct |
190 ms |
7440 KB |
Output is correct |
| 17 |
Correct |
191 ms |
7440 KB |
Output is correct |
| 18 |
Correct |
191 ms |
7440 KB |
Output is correct |
| 19 |
Correct |
188 ms |
7440 KB |
Output is correct |
| 20 |
Correct |
198 ms |
7440 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2045 ms |
6852 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
