답안 #69302 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69302	2018-08-20T11:44:04 Z	FedericoS	Boat (APIO16_boat)	C++14	9 / 100	1673 ms	77932 KB

boat

#pragma GCC optimize("Ofast")
#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]+3;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:70: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

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	504 KB	Output is correct
2	Correct	5 ms	740 KB	Output is correct
3	Correct	6 ms	792 KB	Output is correct
4	Correct	4 ms	792 KB	Output is correct
5	Correct	4 ms	792 KB	Output is correct
6	Correct	5 ms	820 KB	Output is correct
7	Correct	5 ms	820 KB	Output is correct
8	Correct	4 ms	820 KB	Output is correct
9	Correct	6 ms	820 KB	Output is correct
10	Correct	4 ms	820 KB	Output is correct
11	Correct	4 ms	820 KB	Output is correct
12	Correct	5 ms	844 KB	Output is correct
13	Correct	5 ms	844 KB	Output is correct
14	Correct	4 ms	844 KB	Output is correct
15	Correct	5 ms	844 KB	Output is correct
16	Correct	5 ms	844 KB	Output is correct
17	Correct	5 ms	844 KB	Output is correct
18	Correct	4 ms	844 KB	Output is correct
19	Correct	5 ms	844 KB	Output is correct
20	Correct	4 ms	844 KB	Output is correct

Subtask #2
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	504 KB	Output is correct
2	Correct	5 ms	740 KB	Output is correct
3	Correct	6 ms	792 KB	Output is correct
4	Correct	4 ms	792 KB	Output is correct
5	Correct	4 ms	792 KB	Output is correct
6	Correct	5 ms	820 KB	Output is correct
7	Correct	5 ms	820 KB	Output is correct
8	Correct	4 ms	820 KB	Output is correct
9	Correct	6 ms	820 KB	Output is correct
10	Correct	4 ms	820 KB	Output is correct
11	Correct	4 ms	820 KB	Output is correct
12	Correct	5 ms	844 KB	Output is correct
13	Correct	5 ms	844 KB	Output is correct
14	Correct	4 ms	844 KB	Output is correct
15	Correct	5 ms	844 KB	Output is correct
16	Correct	5 ms	844 KB	Output is correct
17	Correct	5 ms	844 KB	Output is correct
18	Correct	4 ms	844 KB	Output is correct
19	Correct	5 ms	844 KB	Output is correct
20	Correct	4 ms	844 KB	Output is correct
21	Correct	1308 ms	15816 KB	Output is correct
22	Correct	1412 ms	15816 KB	Output is correct
23	Correct	1293 ms	15816 KB	Output is correct
24	Correct	1361 ms	15936 KB	Output is correct
25	Correct	1444 ms	16116 KB	Output is correct
26	Correct	1465 ms	16540 KB	Output is correct
27	Correct	1523 ms	16612 KB	Output is correct
28	Correct	1578 ms	16612 KB	Output is correct
29	Correct	1435 ms	16612 KB	Output is correct
30	Incorrect	1673 ms	77932 KB	Output isn't correct
31	Halted	0 ms	0 KB	-

Subtask #3
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	9 ms	77932 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	504 KB	Output is correct
2	Correct	5 ms	740 KB	Output is correct
3	Correct	6 ms	792 KB	Output is correct
4	Correct	4 ms	792 KB	Output is correct
5	Correct	4 ms	792 KB	Output is correct
6	Correct	5 ms	820 KB	Output is correct
7	Correct	5 ms	820 KB	Output is correct
8	Correct	4 ms	820 KB	Output is correct
9	Correct	6 ms	820 KB	Output is correct
10	Correct	4 ms	820 KB	Output is correct
11	Correct	4 ms	820 KB	Output is correct
12	Correct	5 ms	844 KB	Output is correct
13	Correct	5 ms	844 KB	Output is correct
14	Correct	4 ms	844 KB	Output is correct
15	Correct	5 ms	844 KB	Output is correct
16	Correct	5 ms	844 KB	Output is correct
17	Correct	5 ms	844 KB	Output is correct
18	Correct	4 ms	844 KB	Output is correct
19	Correct	5 ms	844 KB	Output is correct
20	Correct	4 ms	844 KB	Output is correct
21	Correct	1308 ms	15816 KB	Output is correct
22	Correct	1412 ms	15816 KB	Output is correct
23	Correct	1293 ms	15816 KB	Output is correct
24	Correct	1361 ms	15936 KB	Output is correct
25	Correct	1444 ms	16116 KB	Output is correct
26	Correct	1465 ms	16540 KB	Output is correct
27	Correct	1523 ms	16612 KB	Output is correct
28	Correct	1578 ms	16612 KB	Output is correct
29	Correct	1435 ms	16612 KB	Output is correct
30	Incorrect	1673 ms	77932 KB	Output isn't correct
31	Halted	0 ms	0 KB	-

답안 #69302

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 0 / 22.0

Subtask #3 0 / 27.0

Subtask #4 0 / 42.0

Subtask #1
9.0 / 9.0

Subtask #2
0 / 22.0

Subtask #3
0 / 27.0

Subtask #4
0 / 42.0