답안 #107758

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
107758	2019-04-25T16:53:41 Z	Just_Solve_The_Problem	Boat (APIO16_boat)	C++11	31 / 100	2000 ms	470264 KB

boat

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = (int)507;
const int mod = (int)1e9 + 7; 

int add(int a, int b) {
	return (a + b) % mod;
}

int mul(int a, int b) {
	return (a * 1LL * b) % mod;
}

int siz = 1;

struct T {
	int l, r, val;
	T() {
		l = r = val = 0;
	}
}tree[(int)4e7];

void upd(int pos, int val, int v = 1, int l = 0, int r = 1e9) {
	if (l == r) {
		tree[v].val = add(tree[v].val, val);
		return ;
	}
	int mid = (l + r) >> 1;
	if (pos <= mid) {
		if (!tree[v].l) 
			tree[v].l = ++siz;
		upd(pos, val, tree[v].l, l, mid);
	} else {
		if (!tree[v].r) 
			tree[v].r = ++siz;
		upd(pos, val, tree[v].r, mid + 1, r);
	}
	tree[v].val = add(tree[tree[v].l].val, tree[tree[v].r].val);
}

int get(int l, int r, int v = 1, int tl = 0, int tr = 1e9) {
	if (tl > r || tr < l || v == 0) return 0;
	if (l <= tl && tr <= r) return tree[v].val;
	int mid = (tl + tr) >> 1;
	return add(get(l, r, tree[v].l, tl, mid), get(l, r, tree[v].r, mid + 1, tr));
}

int n;
int a[N], b[N];

main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &a[i], &b[i]);
	}
	upd(0, 1);
	for (int i = 1; i <= n; i++) {
		for (int j = b[i]; j >= a[i]; j--) {
			upd(j, get(0, j - 1));
		}
	}
	cout << add(get(0, 1e9), mod - 1);
}

Compilation message

boat.cpp:55:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
boat.cpp: In function 'int main()':
boat.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
boat.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a[i], &b[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	547 ms	470116 KB	Output is correct
2	Correct	400 ms	469972 KB	Output is correct
3	Correct	404 ms	470044 KB	Output is correct
4	Correct	415 ms	470008 KB	Output is correct
5	Correct	406 ms	470000 KB	Output is correct
6	Correct	414 ms	470068 KB	Output is correct
7	Correct	390 ms	469980 KB	Output is correct
8	Correct	402 ms	470008 KB	Output is correct
9	Correct	365 ms	470008 KB	Output is correct
10	Correct	374 ms	470008 KB	Output is correct
11	Correct	415 ms	470108 KB	Output is correct
12	Correct	401 ms	470008 KB	Output is correct
13	Correct	365 ms	470008 KB	Output is correct
14	Correct	386 ms	470264 KB	Output is correct
15	Correct	404 ms	470008 KB	Output is correct
16	Correct	383 ms	470200 KB	Output is correct
17	Correct	415 ms	470040 KB	Output is correct
18	Correct	428 ms	469984 KB	Output is correct
19	Correct	438 ms	469988 KB	Output is correct
20	Correct	386 ms	469976 KB	Output is correct

Subtask #2
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	547 ms	470116 KB	Output is correct
2	Correct	400 ms	469972 KB	Output is correct
3	Correct	404 ms	470044 KB	Output is correct
4	Correct	415 ms	470008 KB	Output is correct
5	Correct	406 ms	470000 KB	Output is correct
6	Correct	414 ms	470068 KB	Output is correct
7	Correct	390 ms	469980 KB	Output is correct
8	Correct	402 ms	470008 KB	Output is correct
9	Correct	365 ms	470008 KB	Output is correct
10	Correct	374 ms	470008 KB	Output is correct
11	Correct	415 ms	470108 KB	Output is correct
12	Correct	401 ms	470008 KB	Output is correct
13	Correct	365 ms	470008 KB	Output is correct
14	Correct	386 ms	470264 KB	Output is correct
15	Correct	404 ms	470008 KB	Output is correct
16	Correct	383 ms	470200 KB	Output is correct
17	Correct	415 ms	470040 KB	Output is correct
18	Correct	428 ms	469984 KB	Output is correct
19	Correct	438 ms	469988 KB	Output is correct
20	Correct	386 ms	469976 KB	Output is correct
21	Correct	927 ms	470020 KB	Output is correct
22	Correct	946 ms	470068 KB	Output is correct
23	Correct	925 ms	470180 KB	Output is correct
24	Correct	938 ms	470136 KB	Output is correct
25	Correct	977 ms	470036 KB	Output is correct
26	Correct	1086 ms	470104 KB	Output is correct
27	Correct	1066 ms	470080 KB	Output is correct
28	Correct	1054 ms	470064 KB	Output is correct
29	Correct	961 ms	470152 KB	Output is correct
30	Correct	972 ms	469968 KB	Output is correct
31	Correct	956 ms	469952 KB	Output is correct
32	Correct	1059 ms	470136 KB	Output is correct
33	Correct	993 ms	470224 KB	Output is correct
34	Correct	894 ms	470004 KB	Output is correct
35	Correct	905 ms	470136 KB	Output is correct
36	Correct	939 ms	470108 KB	Output is correct
37	Correct	952 ms	470088 KB	Output is correct
38	Correct	945 ms	470024 KB	Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	547 ms	470116 KB	Output is correct
2	Correct	400 ms	469972 KB	Output is correct
3	Correct	404 ms	470044 KB	Output is correct
4	Correct	415 ms	470008 KB	Output is correct
5	Correct	406 ms	470000 KB	Output is correct
6	Correct	414 ms	470068 KB	Output is correct
7	Correct	390 ms	469980 KB	Output is correct
8	Correct	402 ms	470008 KB	Output is correct
9	Correct	365 ms	470008 KB	Output is correct
10	Correct	374 ms	470008 KB	Output is correct
11	Correct	415 ms	470108 KB	Output is correct
12	Correct	401 ms	470008 KB	Output is correct
13	Correct	365 ms	470008 KB	Output is correct
14	Correct	386 ms	470264 KB	Output is correct
15	Correct	404 ms	470008 KB	Output is correct
16	Correct	383 ms	470200 KB	Output is correct
17	Correct	415 ms	470040 KB	Output is correct
18	Correct	428 ms	469984 KB	Output is correct
19	Correct	438 ms	469988 KB	Output is correct
20	Correct	386 ms	469976 KB	Output is correct
21	Correct	927 ms	470020 KB	Output is correct
22	Correct	946 ms	470068 KB	Output is correct
23	Correct	925 ms	470180 KB	Output is correct
24	Correct	938 ms	470136 KB	Output is correct
25	Correct	977 ms	470036 KB	Output is correct
26	Correct	1086 ms	470104 KB	Output is correct
27	Correct	1066 ms	470080 KB	Output is correct
28	Correct	1054 ms	470064 KB	Output is correct
29	Correct	961 ms	470152 KB	Output is correct
30	Correct	972 ms	469968 KB	Output is correct
31	Correct	956 ms	469952 KB	Output is correct
32	Correct	1059 ms	470136 KB	Output is correct
33	Correct	993 ms	470224 KB	Output is correct
34	Correct	894 ms	470004 KB	Output is correct
35	Correct	905 ms	470136 KB	Output is correct
36	Correct	939 ms	470108 KB	Output is correct
37	Correct	952 ms	470088 KB	Output is correct
38	Correct	945 ms	470024 KB	Output is correct
39	Execution timed out	2051 ms	469944 KB	Time limit exceeded
40	Halted	0 ms	0 KB	-

답안 #107758

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