답안 #68571 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68571	2018-08-17T11:20:43 Z	KLPP	Boat (APIO16_boat)	C++14	31 / 100	2000 ms	525312 KB

boat

#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
typedef long long int lld;
#define MOD 1000000007

struct node{
	int l,r;
	lld val;
	node *left,*right;
};
void build(node *n,int l, int r){
	n->val=0;
	n->l=l;
	n->r=r;
}
void extend(node *n){
	if(n->left!=NULL)return;
	int mid=(n->l+n->r)/2;
	n->left=new node();
	n->right=new node();
	build(n->left,n->l,mid);
	build(n->right,mid+1,n->r);
}
void update(int pos, lld val,node *n){
	if(pos<n->l || pos>n->r)return;
	n->val+=val;
	n->val%=MOD;
	if(n->l!=n->r){
		extend(n);
		update(pos,val,n->left);
		update(pos,val,n->right);
	}
}
lld prefixo(int index, node *n){
	if(n->r<=index)return n->val;
	if(n->l>index || n->val==0) return 0;
	lld ans=prefixo(index,n->left);
	ans+=prefixo(index,n->right);
	return ans%MOD;
}
int main(){
	int n;
	cin>>n;
	pair<lld,lld> arr[n];
	for(int i=0;i<n;i++)cin>>arr[i].first>>arr[i].second;
	vector<lld> DP[n];
	lld responde=0;
	node *segtree=new node();
	build(segtree,1,1000000000);
	for(int i=0;i<n;i++){
		for(int j=arr[i].first;j<=arr[i].second;j++){
			DP[i].push_back((prefixo(j-1,segtree)+1)%MOD);
		}
		for(int j=arr[i].first;j<=arr[i].second;j++){
			update(j,DP[i][j-arr[i].first],segtree);
		}
	}
	/*for(int i=0;i<n;i++){
		for(int j=arr[i].first;j<=arr[i].second;j++){
			cout<<DP[i][j-arr[i].first]<<" ";
		}cout<<endl;
	}*/
	for(int i=0;i<n;i++){
		for(int j=arr[i].first;j<=arr[i].second;j++){
			responde+=DP[i][j-arr[i].first];
			responde%=MOD;
		}
	}
	cout<<responde<<endl;
	
	
	return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	1272 KB	Output is correct
2	Correct	4 ms	1380 KB	Output is correct
3	Correct	5 ms	1584 KB	Output is correct
4	Correct	5 ms	1632 KB	Output is correct
5	Correct	4 ms	1632 KB	Output is correct
6	Correct	5 ms	1632 KB	Output is correct
7	Correct	6 ms	1632 KB	Output is correct
8	Correct	5 ms	1632 KB	Output is correct
9	Correct	4 ms	1632 KB	Output is correct
10	Correct	5 ms	1632 KB	Output is correct
11	Correct	6 ms	1632 KB	Output is correct
12	Correct	5 ms	1632 KB	Output is correct
13	Correct	4 ms	1632 KB	Output is correct
14	Correct	6 ms	1632 KB	Output is correct
15	Correct	4 ms	1632 KB	Output is correct
16	Correct	4 ms	1632 KB	Output is correct
17	Correct	4 ms	1632 KB	Output is correct
18	Correct	3 ms	1632 KB	Output is correct
19	Correct	3 ms	1632 KB	Output is correct
20	Correct	4 ms	1632 KB	Output is correct
21	Correct	476 ms	9724 KB	Output is correct
22	Correct	467 ms	9760 KB	Output is correct
23	Correct	445 ms	9760 KB	Output is correct
24	Correct	544 ms	10016 KB	Output is correct
25	Correct	624 ms	10016 KB	Output is correct
26	Correct	523 ms	10016 KB	Output is correct
27	Correct	535 ms	10016 KB	Output is correct
28	Correct	524 ms	10016 KB	Output is correct
29	Correct	620 ms	10016 KB	Output is correct
30	Correct	629 ms	102884 KB	Output is correct
31	Correct	538 ms	102884 KB	Output is correct
32	Correct	766 ms	102984 KB	Output is correct
33	Correct	565 ms	102984 KB	Output is correct
34	Correct	530 ms	102984 KB	Output is correct
35	Correct	572 ms	102984 KB	Output is correct
36	Correct	574 ms	102984 KB	Output is correct
37	Correct	585 ms	102984 KB	Output is correct
38	Correct	552 ms	102984 KB	Output is correct

Subtask #3
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	2073 ms	525312 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	1272 KB	Output is correct
2	Correct	4 ms	1380 KB	Output is correct
3	Correct	5 ms	1584 KB	Output is correct
4	Correct	5 ms	1632 KB	Output is correct
5	Correct	4 ms	1632 KB	Output is correct
6	Correct	5 ms	1632 KB	Output is correct
7	Correct	6 ms	1632 KB	Output is correct
8	Correct	5 ms	1632 KB	Output is correct
9	Correct	4 ms	1632 KB	Output is correct
10	Correct	5 ms	1632 KB	Output is correct
11	Correct	6 ms	1632 KB	Output is correct
12	Correct	5 ms	1632 KB	Output is correct
13	Correct	4 ms	1632 KB	Output is correct
14	Correct	6 ms	1632 KB	Output is correct
15	Correct	4 ms	1632 KB	Output is correct
16	Correct	4 ms	1632 KB	Output is correct
17	Correct	4 ms	1632 KB	Output is correct
18	Correct	3 ms	1632 KB	Output is correct
19	Correct	3 ms	1632 KB	Output is correct
20	Correct	4 ms	1632 KB	Output is correct
21	Correct	476 ms	9724 KB	Output is correct
22	Correct	467 ms	9760 KB	Output is correct
23	Correct	445 ms	9760 KB	Output is correct
24	Correct	544 ms	10016 KB	Output is correct
25	Correct	624 ms	10016 KB	Output is correct
26	Correct	523 ms	10016 KB	Output is correct
27	Correct	535 ms	10016 KB	Output is correct
28	Correct	524 ms	10016 KB	Output is correct
29	Correct	620 ms	10016 KB	Output is correct
30	Correct	629 ms	102884 KB	Output is correct
31	Correct	538 ms	102884 KB	Output is correct
32	Correct	766 ms	102984 KB	Output is correct
33	Correct	565 ms	102984 KB	Output is correct
34	Correct	530 ms	102984 KB	Output is correct
35	Correct	572 ms	102984 KB	Output is correct
36	Correct	574 ms	102984 KB	Output is correct
37	Correct	585 ms	102984 KB	Output is correct
38	Correct	552 ms	102984 KB	Output is correct
39	Execution timed out	2073 ms	525312 KB	Time limit exceeded
40	Halted	0 ms	0 KB	-

답안 #68571

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 22.0 / 22.0

Subtask #3 0 / 27.0

Subtask #4 0 / 42.0

Subtask #1
9.0 / 9.0

Subtask #2
22.0 / 22.0

Subtask #3
0 / 27.0

Subtask #4
0 / 42.0