oj.uz

Submission #69301

# Submission time Handle Problem Language Result Execution time Memory
69301 2018-08-20T11:42:44 Z FedericoS Boat (APIO16_boat) C++14
9 / 100
 1740 ms 78328 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]+4);

	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=0;i<N;i++){
		X[i]=L[X[i]];
		Y[i]=L[Y[i]];
	}

 
	for(int i=N-1;i>=0;i--)
		for(ll j=X[i],k=0;j<=Y[i];j++,k++){
			DP[i][k]=(somma(j+1)+1)%M;
			aggiungi(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:69:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<V.size();i++)
              ~^~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 552 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 4 ms 700 KB Output is correct
6 Correct 7 ms 712 KB Output is correct
7 Correct 5 ms 724 KB Output is correct
8 Correct 4 ms 864 KB Output is correct
9 Correct 6 ms 876 KB Output is correct
10 Correct 5 ms 876 KB Output is correct
11 Correct 4 ms 876 KB Output is correct
12 Correct 4 ms 876 KB Output is correct
13 Correct 4 ms 876 KB Output is correct
14 Correct 4 ms 892 KB Output is correct
15 Correct 4 ms 904 KB Output is correct
16 Correct 4 ms 904 KB Output is correct
17 Correct 4 ms 904 KB Output is correct
18 Correct 5 ms 904 KB Output is correct
19 Correct 4 ms 904 KB Output is correct
20 Correct 4 ms 904 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 552 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 4 ms 700 KB Output is correct
6 Correct 7 ms 712 KB Output is correct
7 Correct 5 ms 724 KB Output is correct
8 Correct 4 ms 864 KB Output is correct
9 Correct 6 ms 876 KB Output is correct
10 Correct 5 ms 876 KB Output is correct
11 Correct 4 ms 876 KB Output is correct
12 Correct 4 ms 876 KB Output is correct
13 Correct 4 ms 876 KB Output is correct
14 Correct 4 ms 892 KB Output is correct
15 Correct 4 ms 904 KB Output is correct
16 Correct 4 ms 904 KB Output is correct
17 Correct 4 ms 904 KB Output is correct
18 Correct 5 ms 904 KB Output is correct
19 Correct 4 ms 904 KB Output is correct
20 Correct 4 ms 904 KB Output is correct
21 Correct 1427 ms 16060 KB Output is correct
22 Correct 1286 ms 16060 KB Output is correct
23 Correct 1313 ms 16060 KB Output is correct
24 Correct 1380 ms 16212 KB Output is correct
25 Correct 1436 ms 16356 KB Output is correct
26 Correct 1456 ms 16900 KB Output is correct
27 Correct 1541 ms 16924 KB Output is correct
28 Correct 1592 ms 16924 KB Output is correct
29 Correct 1551 ms 17096 KB Output is correct
30 Incorrect 1740 ms 78328 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 78328 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 Correct 4 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 552 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 4 ms 700 KB Output is correct
6 Correct 7 ms 712 KB Output is correct
7 Correct 5 ms 724 KB Output is correct
8 Correct 4 ms 864 KB Output is correct
9 Correct 6 ms 876 KB Output is correct
10 Correct 5 ms 876 KB Output is correct
11 Correct 4 ms 876 KB Output is correct
12 Correct 4 ms 876 KB Output is correct
13 Correct 4 ms 876 KB Output is correct
14 Correct 4 ms 892 KB Output is correct
15 Correct 4 ms 904 KB Output is correct
16 Correct 4 ms 904 KB Output is correct
17 Correct 4 ms 904 KB Output is correct
18 Correct 5 ms 904 KB Output is correct
19 Correct 4 ms 904 KB Output is correct
20 Correct 4 ms 904 KB Output is correct
21 Correct 1427 ms 16060 KB Output is correct
22 Correct 1286 ms 16060 KB Output is correct
23 Correct 1313 ms 16060 KB Output is correct
24 Correct 1380 ms 16212 KB Output is correct
25 Correct 1436 ms 16356 KB Output is correct
26 Correct 1456 ms 16900 KB Output is correct
27 Correct 1541 ms 16924 KB Output is correct
28 Correct 1592 ms 16924 KB Output is correct
29 Correct 1551 ms 17096 KB Output is correct
30 Incorrect 1740 ms 78328 KB Output isn't correct
31 Halted 0 ms 0 KB -