oj.uz

Submission #69298

# Submission time Handle Problem Language Result Execution time Memory
69298 2018-08-20T11:38:50 Z FedericoS Boat (APIO16_boat) C++14
0 / 100
 7 ms 872 KB 
#include <iostream>
#include <unordered_map>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;
 
ll M=1000000007;
int N;
ll X[505],Y[505];
vector<ll> DP[505];
ll ans;
ll R[4000006];
unordered_map<ll,ll> L;
vector<ll> V;
 
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,1e6+1,a,1e6);
}
 
void aggiungi(ll a, ll b){
	insert(1,0,1e6,a,b);
}
 
int main(){
 
	cin>>N;
	for(int i=0;i<N;i++)
		cin>>X[i]>>Y[i];

	for(int i=0;i<N;i++)
		DP[i].resize(Y[i]-X[i]+2);

	for(int i=0;i<N;i++)
		for(int j=X[i];j<Y[i]+1;j++)
			V.push_back(j);

	sort(V.begin(),V.end());
	ll p=0;
	for(int i=0;i<V.size();i++)
		if(i==0 or V[i]!=V[i-1])
			L[V[i]]=p++;
 
	for(int i=N-1;i>=0;i--)
		for(ll j=X[i],k=0;j<=Y[i];j++,k++){
			DP[i][k]=(somma(L[j+1])+1)%M;
			aggiungi(L[j],DP[i][k]);
			ans=(ans+DP[i][k])%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
*/

/*
8
10000 30000
20000 40000
30000 50000
40000 60000
50000 70000
60000 80000
70000 90000
80000 100000
*/

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:68:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<V.size();i++)
              ~^~~~~~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

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