| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 69281 |
2018-08-20T11:13:30 Z |
FedericoS |
Boat (APIO16_boat) |
C++14 |
|
2000 ms |
48524 KB |
#include <iostream>
#include <unordered_map>
#include <map>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;
ll M=1000000007;
int N;
ll X[505],Y[505];
map<ll,ll> S;
map<pll,ll> DP;
ll ans;
unordered_map<ll,ll> R;
ll query(ll k, ll l, ll r, ll a, ll b){
if(b<l or r<a) return 0;
if(a<=l and r<=b) return R[k];
ll m=(l+r)/2;
return (query(2*k,l,m,a,b)+query(2*k+1,m+1,r,a,b))%M;
}
void insert(ll k, ll l, ll r, ll a, ll b){
if(l==r) R[k]=(R[k]+b)%M;
else{
ll m=(l+r)/2;
if(a<=m)
insert(2*k,l,m,a,b);
else
insert(2*k+1,m+1,r,a,b);
R[k]=(R[2*k]+R[2*k+1])%M;
}
}
ll somma(ll a){
return query(1,0,M,a,M-1);
}
void aggiungi(ll a, ll b){
insert(1,0,M,a,b);
}
int main(){
cin>>N;
for(int i=0;i<N;i++)
cin>>X[i]>>Y[i];
for(int i=N-1;i>=0;i--)
for(ll j=X[i];j<=Y[i];j++){
DP[{i,j}]=(somma(j+1)+1)%M;
aggiungi(j,DP[{i,j}]);
ans=(ans+DP[{i,j}])%M;
//cout<<i<<" "<<j<<" "<<DP[{i,j}]<<endl;
}
//for(int i=0;i<10;i++)cout<<i<<" "<<S[i]<<endl;
cout<<ans;
}
/*
3
1 1
2 2
3 3
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
1144 KB |
Output is correct |
| 2 |
Correct |
9 ms |
1392 KB |
Output is correct |
| 3 |
Correct |
9 ms |
1392 KB |
Output is correct |
| 4 |
Correct |
13 ms |
1424 KB |
Output is correct |
| 5 |
Correct |
11 ms |
1424 KB |
Output is correct |
| 6 |
Correct |
9 ms |
1444 KB |
Output is correct |
| 7 |
Correct |
8 ms |
1444 KB |
Output is correct |
| 8 |
Correct |
8 ms |
1444 KB |
Output is correct |
| 9 |
Correct |
9 ms |
1444 KB |
Output is correct |
| 10 |
Correct |
9 ms |
1444 KB |
Output is correct |
| 11 |
Correct |
12 ms |
1444 KB |
Output is correct |
| 12 |
Correct |
10 ms |
1444 KB |
Output is correct |
| 13 |
Correct |
12 ms |
1444 KB |
Output is correct |
| 14 |
Correct |
10 ms |
1444 KB |
Output is correct |
| 15 |
Correct |
10 ms |
1472 KB |
Output is correct |
| 16 |
Correct |
7 ms |
1472 KB |
Output is correct |
| 17 |
Correct |
7 ms |
1472 KB |
Output is correct |
| 18 |
Correct |
8 ms |
1472 KB |
Output is correct |
| 19 |
Correct |
6 ms |
1472 KB |
Output is correct |
| 20 |
Correct |
6 ms |
1472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
1144 KB |
Output is correct |
| 2 |
Correct |
9 ms |
1392 KB |
Output is correct |
| 3 |
Correct |
9 ms |
1392 KB |
Output is correct |
| 4 |
Correct |
13 ms |
1424 KB |
Output is correct |
| 5 |
Correct |
11 ms |
1424 KB |
Output is correct |
| 6 |
Correct |
9 ms |
1444 KB |
Output is correct |
| 7 |
Correct |
8 ms |
1444 KB |
Output is correct |
| 8 |
Correct |
8 ms |
1444 KB |
Output is correct |
| 9 |
Correct |
9 ms |
1444 KB |
Output is correct |
| 10 |
Correct |
9 ms |
1444 KB |
Output is correct |
| 11 |
Correct |
12 ms |
1444 KB |
Output is correct |
| 12 |
Correct |
10 ms |
1444 KB |
Output is correct |
| 13 |
Correct |
12 ms |
1444 KB |
Output is correct |
| 14 |
Correct |
10 ms |
1444 KB |
Output is correct |
| 15 |
Correct |
10 ms |
1472 KB |
Output is correct |
| 16 |
Correct |
7 ms |
1472 KB |
Output is correct |
| 17 |
Correct |
7 ms |
1472 KB |
Output is correct |
| 18 |
Correct |
8 ms |
1472 KB |
Output is correct |
| 19 |
Correct |
6 ms |
1472 KB |
Output is correct |
| 20 |
Correct |
6 ms |
1472 KB |
Output is correct |
| 21 |
Execution timed out |
2070 ms |
16112 KB |
Time limit exceeded |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2060 ms |
48524 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
1144 KB |
Output is correct |
| 2 |
Correct |
9 ms |
1392 KB |
Output is correct |
| 3 |
Correct |
9 ms |
1392 KB |
Output is correct |
| 4 |
Correct |
13 ms |
1424 KB |
Output is correct |
| 5 |
Correct |
11 ms |
1424 KB |
Output is correct |
| 6 |
Correct |
9 ms |
1444 KB |
Output is correct |
| 7 |
Correct |
8 ms |
1444 KB |
Output is correct |
| 8 |
Correct |
8 ms |
1444 KB |
Output is correct |
| 9 |
Correct |
9 ms |
1444 KB |
Output is correct |
| 10 |
Correct |
9 ms |
1444 KB |
Output is correct |
| 11 |
Correct |
12 ms |
1444 KB |
Output is correct |
| 12 |
Correct |
10 ms |
1444 KB |
Output is correct |
| 13 |
Correct |
12 ms |
1444 KB |
Output is correct |
| 14 |
Correct |
10 ms |
1444 KB |
Output is correct |
| 15 |
Correct |
10 ms |
1472 KB |
Output is correct |
| 16 |
Correct |
7 ms |
1472 KB |
Output is correct |
| 17 |
Correct |
7 ms |
1472 KB |
Output is correct |
| 18 |
Correct |
8 ms |
1472 KB |
Output is correct |
| 19 |
Correct |
6 ms |
1472 KB |
Output is correct |
| 20 |
Correct |
6 ms |
1472 KB |
Output is correct |
| 21 |
Execution timed out |
2070 ms |
16112 KB |
Time limit exceeded |
| 22 |
Halted |
0 ms |
0 KB |
- |
