Submission #69275

#TimeUsernameProblemLanguageResultExecution timeMemory
69275FedericoSBoat (APIO16_boat)C++14
0 / 100
2072 ms143844 KiB
#include <iostream>
#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;
map<ll,ll> R;

ll somma(ll a){
	ll res=0;
	for(ll i=a;i<10000;i++)
		res=(res+R[i])%M;
	return res;
}

void aggiungi(ll a, ll b){
	R[a]=(R[a]+b)%M;
}

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...